About

Theory of Induction

Theory

Mathematical induction is a proof technique used to prove that a sequence of statements S1,S2,S3,…S_1, S_2, S_3, \dots is true for all positive integers. It consists of two steps:

  1. Base Case: Prove that S1S_1 is true.
  2. Inductive Step: Assume SkS_k is true (the inductive hypothesis) and prove that Sk+1S_{k+1} is true.

Exercises

Exercise 1
Question

Use mathematical induction to prove that

12+22+32+⋯+n2=n(n+1)(2n+1)61^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}

for all positive integers nn.

Show solution ↓
Solution

Base Case: For n=1n = 1,

12=1(2)(3)6=1.1^2 = \frac{1(2)(3)}{6} = 1.

Thus, the base case holds.

Inductive Hypothesis: Assume

12+22+⋯+k2=k(k+1)(2k+1)6.1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}.

Inductive Step: Then

12+⋯+k2+(k+1)2=k(k+1)(2k+1)6+(k+1)2=(k+1)[k(2k+1)+6(k+1)6]=(k+1)(2k2+7k+6)6=(k+1)(k+2)(2k+3)6.\begin{aligned} 1^2 + \cdots + k^2 + (k+1)^2 &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ &= (k+1)\left[\frac{k(2k+1) + 6(k+1)}{6}\right] \\ &= \frac{(k+1)(2k^2 + 7k + 6)}{6} \\ &= \frac{(k+1)(k+2)(2k+3)}{6}. \end{aligned}

Hence, the formula holds for k+1k+1.

Exercise 2
Question

Prove that

1+3+5+⋯+(2n−1)=n2.1 + 3 + 5 + \cdots + (2n-1) = n^2.
Show solution ↓
Solution

Base Case: For n=1n=1,

1=12.1 = 1^2.

Inductive Hypothesis: Assume

1+3+⋯+(2k−1)=k2.1 + 3 + \cdots + (2k-1) = k^2.

Inductive Step:

k2+(2k+1)=(k+1)2.k^2 + (2k+1) = (k+1)^2.

Thus, the statement holds for all nn.

Exercise 3
Question

Prove that

21+22+23+⋯+2n=2n+1−22^1 + 2^2 + 2^3 + \cdots + 2^n = 2^{n+1} - 2

for all n∈Nn \in \mathbb{N}.

Show solution ↓
Solution

Base Case: For n=1n=1,

2=22−2.2 = 2^{2} - 2.

Inductive Hypothesis: Assume

21+⋯+2k=2k+1−2.2^1 + \cdots + 2^k = 2^{k+1} - 2.

Inductive Step:

21+⋯+2k+2k+1=(2k+1−2)+2k+1=2k+2−2.\begin{aligned} 2^1 + \cdots + 2^k + 2^{k+1} &= (2^{k+1} - 2) + 2^{k+1} \\ &= 2^{k+2} - 2. \end{aligned}
Exercise 4
Question

Show that

1+2+3+⋯+n=n(n+1)2.1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}.
Show solution ↓
Solution

Base Case: For n=1n=1,

1=1(2)2.1 = \frac{1(2)}{2}.

Inductive Hypothesis: Assume

1+2+⋯+k=k(k+1)2.1 + 2 + \cdots + k = \frac{k(k+1)}{2}.

Inductive Step:

k(k+1)2+(k+1)=(k+1)(k+2)2.\frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}.
Exercise 5
Question

Show that 5∣(n5−n)5 \mid (n^5 - n) for all non-negative integers nn.

Show solution ↓
Solution

Base Case: For n=0n=0,

05−0=0,0^5 - 0 = 0,

which is divisible by 55.

Inductive Hypothesis: Assume 5∣(k5−k)5 \mid (k^5 - k).

Inductive Step:

(k+1)5−(k+1)=k5+5k4+10k3+10k2+5k+1−k−1=(k5−k)+5(k4+2k3+2k2+k).\begin{aligned} (k+1)^5 - (k+1) &= k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 - k - 1 \\ &= (k^5 - k) + 5(k^4 + 2k^3 + 2k^2 + k). \end{aligned}

Both terms are divisible by 55, so the result follows.

Exercise 6
Question

For all integers n≥4n \ge 4, prove that

n!>2n.n! > 2^n.
Show solution ↓
Solution

Base Case: For n=4n=4,

4!=24>16=24.4! = 24 > 16 = 2^4.

Inductive Hypothesis: Assume k!>2kk! > 2^k for some k≥4k \ge 4.

Inductive Step:

(k+1)!=(k+1)k!>(k+1)2k>2⋅2k=2k+1,\begin{aligned} (k+1)! &= (k+1)k! \\ &> (k+1)2^k \\ &> 2 \cdot 2^k = 2^{k+1}, \end{aligned}

since k+1≥5>2k+1 \ge 5 > 2. Hence, the inequality holds for all n≥4n \ge 4.