2.1 SUMMATIONS

2.1 SUMMATIONS

1. Prove by induction on $n >= 0$ that $$\sum_{i=1}^n i = n(n+1)/2$$

1-1. Basis Condition

---

n = 1일 때 성립하는가?

$$\sum_{i=1}^1 i = 1(1+1)/2 = 1$$
이므로 성립한다.

1-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$\sum_{i=1}^k i = k(k+1)/2$$
가 성립한다고 하자.

1-3. Induction Proof (가정을 이용한 증명)

---

n = k + 1일 때를 증명해보자

$$\sum_{i=1}^{k+1} i = (k+1)(k+2)/2$$
가 성립함을 증명해야 한다.

이는 1~k 까지의 합 + (k+1) 이므로..

$$(k+1) + \sum_{i=1}^k i = (k+1)+k(k+1)/2$$
이다.

위 식을 정리하면
$$
\begin{aligned}
k(k+1)/2 + (k+1)
& =(k^2 + k + 2(k+1))/2
\\ & =(k^2 + 3k + 2)/2
\\ & =(k+1)(k+2)/2
\end{aligned}
$$
이므로

k + 1 일때도 성립함을 알 수 있다.

2. Prove by induction on $n>=0$ that $$\sum_{i=1}^n i^2 = n(n+1)(2n+1)/6$$

2-1. Basis Condition

---

n = 1일 때 성립하는가?
$$\sum_{i=1}^1 i^2 = 1(1+1)(2+1)/6 = 1$$
이므로 성립한다.

2-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.
$$\sum_{i=1}^k i^2 = k(k+1)(2k+1)/6$$
를 만족한다.

2-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\sum_{i=1}^{k+1} i^2 = (k+1)(k+2)(2k+3)/6
$$
를 증명해야 한다.

이는
$$
\begin{aligned}
\sum_{i=1}^{k+1} i^2
&= (k+1)^2 + \sum_{i=1}^k i^2 \\
&= (k+1)^2+ k(k+1)(2k+1)/6 \\
\end{aligned}
$$
이므로

$$
\begin{aligned}
(k+1)(2k^2+k+6k+6)/6
&= (k+1)(2k^2+7k+6)/6 \\
&= (k+1)(k+2)(2k+3)/6 \\
\end{aligned}
$$

이므로

k + 1일때도 성립함을 알 수 있다.

3. Prove by induction on $n>=0$ that $$\sum_{i=1}^n i^3 = n^2(n+1)^2/4$$

3-1. Basis Condition

---

n = 1일 때 성립하는가?

$$\sum_{i=1}^1 1^3 = 1^2(1+1)^2/4$$
이므로 성립한다.

3-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.
$$\sum_{i=1}^k i^3 = k^2(k+1)^2/4$$
를 만족한다.

3-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\sum_{i=1}^{k+1} i^3 = (k+1)^2((k+1)+1)^2/4
$$
를 증명해야 한다.

이는
$$
\sum_{i=1}^{k+1} i^3 = (k+1)^3 + \sum_{i=1}^{k} i^3 = (k+1)^3+k^2(k+1)^2/4
$$
이므로

$$
\begin{aligned}
(k+1)^3+k^2(k+1)^2/4
&=(k+1)^2(4k+4+k^2)/4\\
&=(k+1)^2(k+2)^2/4\\
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

4. Prove by induction on $n>=0$ that $$\sum_{i=0}^n (2i+1)^2 = (n+1)(2n+1)(2n+3)/3$$

4-1. Basis Condition

---

n = 1일 때 성립하는가?

$$\sum_{i=1}^1 (2i+1)^2 = (1+1)(2+1)(2+3)/3 = 10$$
이므로 성립한다.

4-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.
$$\sum_{i=1}^k (2i+1)^2 = (k+1)(2k+1)(2k+3)/3$$
를 만족한다고 하자.

4-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1} (2i+1)^2
&= ((k+1)+1)(2(k+1)+1)(2(k+1)+3)/3 \\
&= (k+2)(2k+3)(2k+5)/3 \\
\end{aligned}
$$
을 증명해야 한다.

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1} (2i+1)^2
&= (2(k+1)+1)^2 + \sum_{i=1}^k (2i+1)^2 \\
&=(2k+3)^2 + (k+1)(2k+1)(2k+3)/3 \\
&=(2k+3)((6k+9)+(2k^2+k+2k+1))/3 \\
&=(k+2)(2k+3)(2k+5)/3
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

5. Prove by induction on $n>=0$ that $$\sum_{i=1}^n i(i+1) = n(n+1)(n+2)/3$$

5-1. Basis Condition

---

n = 1일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^1 i(i+1) &= 1(1+1)(1+2)/3 \\
&= 1(1+1) \\
&= 2
\end{aligned}
$$

이므로 성립한다.

5-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^k i(i+1) = k(k+1)(k+2)/3
\end{aligned}
$$
를 만족한다.

5-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1} i(i+1) = (k+1)(k+2)(k+3)/3
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1} i(i+1) &= (k+1)(k+2) + \sum_{i=1}^k i(i+1) \\
&= (k+1)(k+2) + k(k+1)(k+2)/3 \\
&= (k+1)(k+2)(k+3)/3
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

6. Prove by induction on $n>=0$ that $$\sum_{i=1}^n i(i+1)(i+2) = n(n+1)(n+2)(n+3)/4$$

6-1. Basis Condition

---

n = 1일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^1 i(i+1)(i+2) &= 1(1+1)(1+2)(1+3)/4\\
&= 1(2)(3)(4)/4 \\
&= 6
\end{aligned}
$$

이므로 성립한다.

6-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^k i(i+1)(i+2) = k(k+1)(k+2)(k+3)/4
\end{aligned}
$$
를 만족한다.

6-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1} i(i+1)(i+2) = (k+1)(k+2)(k+3)(k+4)/4
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1} i(i+1)(i+2) &= (k+1)(k+2)(k+3) + \sum_{i=1}^k i(i+1)(i+2) \\
&= (k+1)(k+2)(k+3) + k(k+1)(k+2)(k+3)/4 \\
&=(k+1)(k+2)(k+3)(k+4)/4
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

7. Prove by induction on $n>=0$ that $$\sum_{i=1}^n i*i! = (n+1)!-1$$

7-1. Basis Condition

---

n = 1일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^1 i*i! &= (1+1)!-1\\
&= (2)! -1 \\
&= 1
\end{aligned}
$$

이므로 성립한다.

7-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^k i*i! = (k+1)!-1
\end{aligned}
$$
를 만족한다.

7-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1} i*i! &= ((k+1)+1)!-1
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1} i_i! &= (k+1)(k+1)! + \sum_{i=1}^k i_i! \\
&= (k+1)(k+1)! + (k+1)!-1 \\
&= (k+1+1)(k+1)!-1 \\
&= (k+2)(k+1)!-1
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

8. Prove by induction on $n>=1$ that $$\sum_{i=1}^n 1/2^i = 1-1/2^n$$

8-1. Basis Condition

---

n = 1일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^1 1/2^i &= 1-1/2^1 \\
&= 1-1/2 \\
&= 1/2
\end{aligned}
$$

이므로 성립한다.

8-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^k 1/2^i = 1-1/2^k
\end{aligned}
$$
를 만족한다.

8-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1} 1/2^i = 1-1/2^{k+1}
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1} 1/2^i &= 1/2^{k+1}+ \sum_{i=1}^k 1/2^i\\
&= 1/2^{k+1} + 1-1/2^k \\
&= 1-(2-1)/2^{k+1} \\
&= 1-1/2^{k+1}
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

9. Prove by induction on $n>=1$ that for every $a != 1$ $$\sum_{i=0}^n a^i = \frac{a^{n+1}-1}{a-1}$$

9-1. Basis Condition

---

n = 2일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=0}^2 a^i &= \frac{a^{2+1}-1}{a-1} \\
&= \frac{a^3 -1}{a-1} \\
&= \frac{(a-1)(a^2+a+1)}{(a-1)} \\
&= a^2+a+1 \\
&= 1 + a + a^2
\end{aligned}
$$

이므로 성립한다.

9-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=0}^k a^i = \frac{a^{k+1}-1}{a-1}
\end{aligned}
$$
를 만족한다.

9-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=0}^{k+1} a^i = \frac{a^{(k+1)+1}-1}{a-1}
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=0}^{k+1} a^i &= a^{k+1} + \sum_{i=0}^k a^i \\
&= a^{k+1} + \frac{a^{k+1}-1}{a-1}\\
&= \frac{a^{k+2}-a^{k+1} + a^{k+1}-1}{a-1} \\
&= \frac{a^{k+2}-1}{a-1}
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

**10. Prove by induction on $n \geq 0$ that for every $a \neq 1$, and all $0 \leq j \leq n$ $$\sum_{i=j}^n a^i = \frac{a^{n+1}-a^j}{a-1}$$

10-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=j}^0 a^i &= \frac{a^{0+1}-a^j}{a-1} \\
&= \frac{a^{1}-a^0}{a-1} \\
&= 1
\end{aligned}
$$

j = n 일때 성립하는가?

$$
\begin{aligned}
\sum_{i=n}^n a^i &= \frac{a^{n+1}-a^n}{a-1} \\
&= a^n\frac{a^{1}-a^0}{a-1} \\
&= a^n
\end{aligned}
$$

이므로 성립한다.

10-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=j}^k a^i = \frac{a^{k+1}-a^j}{a-1}
\end{aligned}
$$
를 만족한다.

10-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=j}^{k+1} a^i = \frac{a^{(k+1)+1}-a^j}{a-1}
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=j}^{k+1} a^i &= a^{k+1} + \sum_{i=j}^k a^i \\
& 0 \leq j \leq k \\
&= a^{k+1} + \frac{a^{k+1}-a^j}{a-1} \\
&= \frac{a^{k+2}-a^{k+1}+ a^{k+1}-a^j}{a-1} \\
&= \frac{a^{k+2}-a^j}{a-1}
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

**11. Prove by induction on $n \geq 0$ that $$\sum_{i=0}^n 2^i = 2^{n+1}-1$$

11-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=0}^0 2^i &= 2^{0+1}-1 \\
&= 1
\end{aligned}
$$

이므로 성립한다.

11-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=0}^k 2^i &= 2^{k+1}-1
\end{aligned}
$$
를 만족한다.

11-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=0}^{k+1} 2^i &= 2^{(k+1)+1}-1 \\
&= 2^{k+2}-1
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=0}^{k+1} 2^i &= 2^{k+1}+\sum_{i=0}^k 2^i \\
&=2^{k+1}+2^{k+1}-1\\
&=2^{k+2}-1
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

12. Prove by induction on $n \geq 1$ that $$\sum_{i=1}^n \frac{1}{i(i+1)} = \frac{n}{n+1}$$

12-1. Basis Condition

---

n = 1일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^1 \frac{1}{i(i+1)} &= \frac{1}{1+1} \\
&= \frac{1}{2}
\end{aligned}
$$

이므로 성립한다.

12-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^k \frac{1}{i(i+1)} = \frac{k}{k+1}
\end{aligned}
$$
를 만족한다.

12-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1}\frac{1}{i(i+1)} &= \frac{k+1}{(k+1)+1}\\
&=\frac{k+1}{k+2}
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1}\frac{1}{i(i+1)} &= \frac{1}{(k+1)(k+2)}+ \sum_{i=1}^{k+1}\frac{1}{i(i+1)} \\
&=\frac{1}{(k+1)(k+2)}+\frac{k}{k+1} \\
&=\frac{1+k(k+2)}{(k+1)(k+2)}\\
&=\frac{1+k^2+2k}{(k+1)(k+2)}\\
&=\frac{(k+1)^2}{(k+1)(k+2)}\\
&=\frac{k+1}{k+2}\\
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

13. Prove by induction on $n \geq 0$ that $$\sum_{i=1}^n i2^i = (n-1)2^{n+1}+2$$

13-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^0 i2^i &= (0-1)2^{0+1}+2 \\
&= -2 + 2 \\
&= 0
\end{aligned}
$$

이므로 성립한다.

13-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^k i2^i = (k-1)2^{k+1}+2
\end{aligned}
$$
를 만족한다.

13-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1} i2^i &= ((k+1)-1)2^{(k+1)+1}+2 \\
&= k2^{k+2}+2
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1} i2^i &= (k+1)2^{k+1}+\sum_{i=1}^k i2^i \\
&=(k+1)2^{k+1}+(k-1)2^{k+1}+2 \\
&=2k2^{k+1}+2 \\
&=k2^{k+2}+2 \\
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

14. Prove by induction on $n \geq 0$ that for every $a \neq 1$, $$\sum_{i=1}^n ia^i = \frac{na^{n+2}-(n+1)a^{n+1}+a}{(a-1)^2}$$

14-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^0 ia^i &= \frac{0a^{0+2}-(0+1)a^{0+1}+a}{(a-1)^2} \\
&= \frac{-a^{1}+a}{(a-1)^2} \\
&= \frac{0}{(a-1)^2} \\
&= 0 \\
\end{aligned}
$$

이므로 성립한다.

14-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^k ia^i = \frac{ka^{k+2}-(k+1)a^{k+1}+a}{(a-1)^2}
\end{aligned}
$$
를 만족한다.

14-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1} ia^i &= \frac{(k+1)a^{(k+1)+2}-((k+1)+1)a^{(k+1)+1}+a}{(a-1)^2} \\
&= \frac{(k+1)a^{k+3}-(k+2)a^{k+2}+a}{(a-1)^2} \\
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1} ia^i &= (k+1)a^{k+1} +\sum_{i=1}^k ia^i\\
&= (k+1)a^{k+1} +\frac{ka^{k+2}-(k+1)a^{k+1}+a}{(a-1)^2} \\
&= \frac{(a-1)^2(k+1)a^{k+1}+ ka^{k+2}-(k+1)a^{k+1}+a}{(a-1)^2} \\
&= \frac{(a^2-2a+1)(k+1)a^{k+1}+ ka^{k+2}-(k+1)a^{k+1}+a}{(a-1)^2} \\
&= \frac{(ka^2-2ak+k+a^2-2a+1)a^{k+1}+ ka^{k+2}-(k+1)a^{k+1}+a}{(a-1)^2} \\
&= \frac{ka^{k+3}-2ka^{k+2}+ka^{k+1}+a^{k+3}-2a^{k+2}+a^{k+1}+ka^{k+2}-(k+1)a^{k+1}+a}{(a-1)^2} \\
&= \frac{(k+1)a^{k+3}+(-2k-2+k)a^{k+2}+(k+1-(k+1))a^{k+1}+a}{(a-1)^2} \\
&= \frac{(k+1)a^{k+3}+(-k-2)a^{k+2}+a}{(a-1)^2} \\
&= \frac{(k+1)a^{k+3}-(k+2)a^{k+2}+a}{(a-1)^2} \\
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

15. Prove by induction on $n \geq 0$ that $$\sum\_{i=1}^n i^22^i = n^22^{n+1} -n2^{n+2}+3_2^{n+1}-6$$

15-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^0 i^22^i &= 0^22^{0+1} -02^{0+2}+3*2^{0+1}-6 \\
&= 0-0+6-6 \\
&= 0
\end{aligned}
$$

이므로 성립한다.

15-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^k i^22^i = k^22^{k+1} -k2^{k+2}+3*2^{k+1}-6
\end{aligned}
$$

를 만족한다.

15-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1} i^22^i &= (k+1)^22^{(k+1)+1} -(k+1)2^{(k+1)+2}+3_2^{(k+1)+1}-6 \\
&=(k+1)^22^{k+2} -(k+1)2^{k+3}+3_2^{k+2}-6 \\
&=((k+1)^2+3)2^{k+2} -(k+1)2^{k+3}-6 \\
&=(k^2+2k+4)2^{k+2} -(k+1)2^{k+3}-6 \\
&=(k^2+2k+4-2k-2)2^{k+2}-6 \\
&=(k^2+2)2^{k+2}-6 \\
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1} i^22^i &= (k+1)^22^{k+1} + \sum_{i=1}^k i^22^i \\
&= (k+1)^22^{k+1} +k^22^{k+1} -k2^{k+2}+3*2^{k+1}-6 \\
&= ((k+1)^2+k^2+3)2^{k+1} -k2^{k+2}-6 \\
&= (2k^2+2k+4)2^{k+1} -k2^{k+2}-6 \\
&= (k^2+k+2)2^{k+2} -k2^{k+2}-6 \\
&= (k^2+k+2-k)2^{k+2}-6 \\
&= (k^2+2)2^{k+2}-6 \\
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

16. Prove by induction on $n \geq 0$ that $$\sum_{i=1}^n i^22^{n-i} = 2^{n+3} - 2^{n+1} -n^2-4n-6$$

16-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^0 i^22^{0-i} &= 2^{0+3} - 2^{0+1} -0^2-4*0-6 \\
&= 2^3-2-6 \\
&= 0
\end{aligned}
$$

이므로 성립한다.

16-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^k i^22^{k-i} &= 2^{k+3} - 2^{k+1} -k^2-4k-6
\end{aligned}
$$

를 만족한다.

16-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1} i^22^{(k+1)-i} &= 2^{(k+1)+3} - 2^{(k+1)+1} -(k+1)^2-4(k+1)-6 \\
&= 2^{k+4} - 2^{k+2} -(k+1)^2-4(k+1)-6 \\
&= 2^{k+4} - 2^{k+2} -(k^2+2k+1)-4k-4-6 \\
&= 2^{k+4} - 2^{k+2} -k^2-6k-11 \\
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1} i^22^{(k+1)-i} &= (k+1)^22^{(k+1)-(k+1)} + 2\sum_{i=1}^k i^22^{k-i} \\
&= (k+1)^22^{0} + 2\sum_{i=1}^k i^22^{k-i} \\
&= (k+1)^2 + 2\sum_{i=1}^k i^22^{k-i} \\
&= (k+1)^2 + 2(2^{k+3} - 2^{k+1} -k^2-4k-6) \\
&= (k+1)^2 + (2^{k+4} - 2^{k+2} -2k^2-8k-12) \\
&= (k^2+2k+1-2k^2-8k-12) +2^{k+4}-2^{k+2}\\
&= (-k^2-6k-11) +2^{k+4}-2^{k+2}\\
&= 2^{k+4} - 2^{k+2} -k^2-6k-11 \\
\end{aligned}
$$
이므로

k + 1일때도 성립함을 알 수 있다.

17. Prove by induction on $n \geq 0$ that $$\sum_{i=1}^n \frac{1}{n+i} = \sum_{i=1}^n (\frac{1}{2i-1}-\frac{1}{2i})$$

17-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^0 \frac{1}{0+i} &= \sum_{i=1}^0 (\frac{1}{2i-1}-\frac{1}{2i}) \\
&= 0
\end{aligned}
$$

이므로 성립한다.

17-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^k \frac{1}{k+i} = \sum_{i=1}^k (\frac{1}{2i-1}-\frac{1}{2i})
\end{aligned}
$$

를 만족한다.

17-3. Induction Proof (가정을 이용한 증명)

---

n = k일 때 성립한다고 가정한 뒤,

n = k+1일 때 성립하는지 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1} \frac{1}{(k+1)+i} &= \sum_{i=1}^{k+1} (\frac{1}{2i-1}-\frac{1}{2i}) \\
&= (\frac{1}{2(k+1)-1}-\frac{1}{2(k+1)})+\sum_{i=1}^{k} (\frac{1}{2i-1}-\frac{1}{2i})\\
&= (\frac{1}{2k+1}-\frac{1}{2k+2})+\sum_{i=1}^{k} (\frac{1}{2i-1}-\frac{1}{2i})\\
\end{aligned}
$$

이는

$$
\begin{aligned}
\sum_{i=1}^{k+1} \frac{1}{(k+1)+i} &= \frac{1}{(k+1)+(k+1)} +\sum_{i=1}^k \frac{1}{(k+1)+i}\\
&= \frac{1}{2k+2} -\frac{1}{k+1}+\sum_{i=0}^k \frac{1}{(k+1)+i}\\
i+1 = t;치환\\
&= \frac{1}{2k+2} -\frac{1}{k+1}+\sum_{t=1}^{k+1} \frac{1}{k+t}\\
&= \frac{1}{2k+2} -\frac{1}{k+1}+\frac{1}{2k+1}+\sum_{t=1}^{k} \frac{1}{k+t}\\
&= \frac{1}{2k+2} -\frac{1}{k+1}+\frac{1}{2k+1}+\sum_{i=1}^k (\frac{1}{2i-1}-\frac{1}{2i})\\
&= -\frac{1}{2k+2}+\frac{1}{2k+1}+\sum_{i=1}^k (\frac{1}{2i-1}-\frac{1}{2i})\\
&= (\frac{1}{2k+1}-\frac{1}{2k+2})+\sum_{i=1}^{k} (\frac{1}{2i-1}-\frac{1}{2i})\\
\end{aligned}
$$

이므로

k + 1일때도 성립함을 알 수 있다.