About

Induction Exercise Set

Theory

Use mathematical induction to prove that the following assertions are true for all n≥1n \ge 1.

Exercises

Exercise 1
Question

Prove that

13+23+33+⋯+n3=14n2(n+1)2.1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{1}{4} n^2 (n+1)^2.
Show solution ↓
Solution

Base Case: For n=1n=1,

13=14(1)2(2)2=1.1^3 = \frac{1}{4}(1)^2(2)^2 = 1.

Thus, the base case holds.

Inductive Hypothesis: Assume

13+23+⋯+k3=14k2(k+1)2.1^3 + 2^3 + \cdots + k^3 = \frac{1}{4} k^2 (k+1)^2.

Inductive Step:

13+⋯+k3+(k+1)3=14k2(k+1)2+(k+1)3=(k+1)2(k2+4k+44)=(k+1)2(k+2)24.\begin{aligned} 1^3 + \cdots + k^3 + (k+1)^3 &= \frac{1}{4} k^2 (k+1)^2 + (k+1)^3 \\ &= (k+1)^2\left( \frac{k^2 + 4k + 4}{4} \right) \\ &= \frac{(k+1)^2 (k+2)^2}{4}. \end{aligned}
Exercise 2
Question

Prove that

11⋅2+12⋅3+⋯+1n(n+1)=nn+1.\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1}.
Show solution ↓
Solution

Base Case: For n=1n=1,

12=12.\frac{1}{2} = \frac{1}{2}.

Inductive Hypothesis: Assume

11⋅2+⋯+1k(k+1)=kk+1.\frac{1}{1 \cdot 2} + \cdots + \frac{1}{k(k+1)} = \frac{k}{k+1}.

Inductive Step:

kk+1+1(k+1)(k+2)=k(k+2)+1(k+1)(k+2)=(k+1)2(k+1)(k+2)=k+1k+2.\begin{aligned} \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} &= \frac{k(k+2) + 1}{(k+1)(k+2)} \\ &= \frac{(k+1)^2}{(k+1)(k+2)} \\ &= \frac{k+1}{k+2}. \end{aligned}
Exercise 3
Question

Prove that

11+12+13+⋯+12n≥1+n2.\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^n} \ge 1 + \frac{n}{2}.
Show solution ↓
Solution

Base Case: For n=1n=1,

1+12=1+12.1 + \frac{1}{2} = 1 + \frac{1}{2}.

Inductive Hypothesis: Assume

11+⋯+12k≥1+k2.\frac{1}{1} + \cdots + \frac{1}{2^k} \ge 1 + \frac{k}{2}.

Inductive Step: From 2k+12^k+1 to 2k+12^{k+1} there are 2k2^k terms, each at least 12k+1\frac{1}{2^{k+1}}. Hence, the added sum is at least

2k⋅12k+1=12.2^k \cdot \frac{1}{2^{k+1}} = \frac{1}{2}.

Therefore,

11+⋯+12k+1≥(1+k2)+12=1+k+12.\frac{1}{1} + \cdots + \frac{1}{2^{k+1}} \ge \left(1 + \frac{k}{2}\right) + \frac{1}{2} = 1 + \frac{k+1}{2}.
Exercise 4
Question

Prove that

112+122+132+⋯+1n2≤2−1n.\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \cdots + \frac{1}{n^2} \le 2 - \frac{1}{n}.
Show solution ↓
Solution

Base Case: For n=1n=1,

1=2−1.1 = 2 - 1.

Inductive Hypothesis: Assume

112+⋯+1k2≤2−1k.\frac{1}{1^2} + \cdots + \frac{1}{k^2} \le 2 - \frac{1}{k}.

Inductive Step:

112+⋯+1(k+1)2≤2−1k+1(k+1)2lt;2−1k+1k(k+1)=2−1k+1.\begin{aligned} \frac{1}{1^2} + \cdots + \frac{1}{(k+1)^2} &\le 2 - \frac{1}{k} + \frac{1}{(k+1)^2} \\ &< 2 - \frac{1}{k} + \frac{1}{k(k+1)} \\ &= 2 - \frac{1}{k+1}. \end{aligned}
Exercise 5
Question

Prove that

12!+23!+34!+⋯+n(n+1)!=1−1(n+1)!.\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \cdots + \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}.
Show solution ↓
Solution

Base Case: For n=1n=1,

12!=1−12!.\frac{1}{2!} = 1 - \frac{1}{2!}.

Inductive Hypothesis: Assume

12!+⋯+k(k+1)!=1−1(k+1)!.\frac{1}{2!} + \cdots + \frac{k}{(k+1)!} = 1 - \frac{1}{(k+1)!}.

Inductive Step:

1−1(k+1)!+k+1(k+2)!=1−(k+2)−(k+1)(k+2)!=1−1(k+2)!.\begin{aligned} 1 - \frac{1}{(k+1)!} + \frac{k+1}{(k+2)!} &= 1 - \frac{(k+2)-(k+1)}{(k+2)!} \\ &= 1 - \frac{1}{(k+2)!}. \end{aligned}