Mathematical Induction Examples with Step-by-Step Solutions, Including Strong Induction

1. Let $P(n)$: $1 + 3 + \cdots + (2n - 1) = n^2$

2. Base case $n = 1$: left side $= 1$, right side $= 1^2 = 1$. True.

3. Assume $1 + 3 + \cdots + (2k - 1) = k^2$. We must show $1 + 3 + \cdots + (2k + 1) = (k+1)^2$.

4. $\underbrace{1 + 3 + \cdots + (2k - 1)}_{= k^2\ \text{(hypothesis)}} + (2k + 1) = k^2 + 2k + 1 = (k+1)^2$ ✓

By the principle of mathematical induction, $P(n)$ is true for all $n \ge 1$. ∎

1. Base case $n = 1$: left side $= 1\cdot 2 = 2$, right side $= \dfrac{1\cdot2\cdot3}{3} = 2$. True.

2. Assume it holds for $n = k$. We must show the sum up to the term $(k+1)(k+2)$ equals $\dfrac{(k+1)(k+2)(k+3)}{3}$.

3. $\dfrac{k(k+1)(k+2)}{3} + (k+1)(k+2) = \dfrac{(k+1)(k+2)\,(k + 3)}{3}$ (factor out $(k+1)(k+2)$ instead of expanding) ✓

True for all $n \ge 1$. Tip: always write the target first, so you know which common factor to pull out.

1. Base case $n = 1$: left side $= 1$, right side $= \dfrac{1\cdot2\cdot3}{6} = 1$. True.

2. Assume $1^2 + \cdots + k^2 = \dfrac{k(k+1)(2k+1)}{6}$. Target: $1^2 + \cdots + (k+1)^2 = \dfrac{(k+1)(k+2)(2k+3)}{6}$.

3. $\dfrac{k(k+1)(2k+1)}{6} + (k+1)^2 = \dfrac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} = \dfrac{(k+1)(2k^2 + 7k + 6)}{6}$

4. $2k^2 + 7k + 6 = (k+2)(2k+3)$, so the sum equals $\dfrac{(k+1)(k+2)(2k+3)}{6}$ ✓

True for all $n \ge 1$. The target told us to look for the factors $(k+2)$ and $(2k+3)$ in the bracket.

1. Base case $n = 1$: $4 - 1 = 3 = 3\cdot1$, divisible.

2. Assume $4^k - 1 = 3m$ for some integer $m$.

3. $4^{k+1} - 1 = 4\cdot 4^k - 1 = 4(4^k - 1) + 3 = 4(3m) + 3 = 3(4m + 1)$, divisible by 3 ✓

True for all $n \ge 1$. The key trick: add and subtract to create $4(4^k - 1)$, which is the hypothesis.

1. Base case $n = 1$: $7 - 2 = 5$, divisible.

2. Assume $7^k - 2^k = 5m$ for some integer $m$.

3. $7^{k+1} - 2^{k+1} = 7\cdot7^k - 2\cdot2^k = 7(7^k - 2^k) + 7\cdot2^k - 2\cdot2^k = 7(5m) + 5\cdot2^k = 5(7m + 2^k)$ ✓

True for all $n \ge 1$. With two different bases, add and subtract $7\cdot2^k$ so that one bracket is exactly $f(k)$.

1. Base case $n = 1$: $1 - 1 = 0 = 6\cdot0$, divisible.

2. Assume $k^3 - k = 6m$.

3. $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k(k+1) = 6m + 3k(k+1)$

4. $k(k+1)$ is a product of two consecutive integers, so it is even: $k(k+1) = 2j$. Then $3k(k+1) = 6j$ and the total is $6(m + j)$ ✓

True for all $n \ge 1$. The step needs one extra fact (consecutive integers include an even number); state it clearly instead of hiding it.

1. Why start at 5: $n = 2, 3, 4$ give $4 = 4,\ 8 < 9,\ 16 = 16$, which are false.

2. Base case $n = 5$: $2^5 = 32 > 25$. True.

3. Assume $2^k > k^2$ ($k \ge 5$): $2^{k+1} = 2\cdot 2^k > 2k^2$

4. $2k^2 - (k+1)^2 = (k-1)^2 - 2 > 0$ for $k \ge 3$, so $2^{k+1} > 2k^2 > (k+1)^2$ ✓

True for all $n \ge 5$.

1. Why start at 4: $1! = 1 < 2,\ 2! = 2 < 4,\ 3! = 6 < 8$, but $4! = 24 > 16$.

2. Base case $n = 4$: $24 > 16$. True.

3. Assume $k! > 2^k$ ($k \ge 4$): $(k+1)! = (k+1)\cdot k! > (k+1)\cdot 2^k$

4. Since $k + 1 \ge 5 > 2$: $(k+1)\cdot2^k > 2\cdot 2^k = 2^{k+1}$ ✓

True for all $n \ge 4$. This is why the terms $x^n/n!$ of the exponential series shrink so fast.

1. Base case $n = 1$: $1 + x \ge 1 + x$. True.

2. Assume $(1 + x)^k \ge 1 + kx$.

3. Multiply both sides by $1 + x$, which is allowed without flipping the sign because $1 + x \ge 0$: $(1 + x)^{k+1} \ge (1 + x)(1 + kx) = 1 + (k+1)x + kx^2$

4. $kx^2 \ge 0$, so $(1 + x)^{k+1} \ge 1 + (k+1)x$ ✓

True for all $n \ge 1$, $x \ge -1$. The condition $x \ge -1$ is used in exactly one line: multiplying an inequality by $1 + x$.

1. First terms: $1, 3, 7, 15, \dots$, one less than $2, 4, 8, 16$, which suggests $2^n - 1$.

2. Base case $n = 1$: $a_1 = 1 = 2^1 - 1$. True.

3. Assume $a_k = 2^k - 1$: $a_{k+1} = 2a_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 1$ ✓

$a_n = 2^n - 1$ for all $n \ge 1$. This is the number of moves in the Tower of Hanoi with n discs.

1. Base case $n = 1$: product rule, $\dfrac{d}{dx}(xe^x) = e^x + xe^x = (x + 1)e^x$. True.

2. Assume $\dfrac{d^k}{dx^k}(xe^x) = (x + k)e^x$.

3. $\dfrac{d^{k+1}}{dx^{k+1}}(xe^x) = \dfrac{d}{dx}\big[(x + k)e^x\big] = e^x + (x + k)e^x = (x + k + 1)e^x$ ✓

True for all $n \ge 1$. At $x = 0$ the nth derivative is $n$, which gives the Maclaurin series $xe^x = \sum_{n\ge1} \dfrac{x^n}{(n-1)!}$; see what the Taylor series is.

1. Base case $n = 2$: 2 is prime. True.

2. Strong hypothesis: assume every integer $j$ with $2 \le j \le k$ is a prime or a product of primes.

3. Consider $k + 1$. If it is prime, we are done. If not, $k + 1 = ab$ with $2 \le a \le k$ and $2 \le b \le k$.

4. By the hypothesis, $a$ and $b$ are each a prime or a product of primes, so $ab = k + 1$ is a product of primes ✓

True for all $n \ge 2$. Ordinary induction fails here: knowing about $k$ tells you nothing about the factors of $k + 1$, which can be any smaller numbers.

1. Base cases (three of them): $8 = 3 + 5,\ 9 = 3 + 3 + 3,\ 10 = 5 + 5$

2. Strong hypothesis: let $k \ge 10$ and assume every amount from 8 to $k$ cents can be made.

3. $k + 1 = (k - 2) + 3$, and $8 \le k - 2 \le k$, so $k - 2$ can be made by the hypothesis. Add one 3-cent stamp ✓

Every amount from 8 cents up can be made (7 cents cannot). The step reaches back 3 places, so it needs 3 base cases; with only $n = 8$ checked, the step from 8 to 9 would rely on $9 - 3 = 6$, which was never shown.

1. Base cases (two, because the recurrence uses two previous terms): $a_1 = 2 - 1 = 1$ and $a_2 = 4 + 1 = 5$. True.

2. Strong hypothesis: let $k \ge 2$ and assume $a_j = 2^j + (-1)^j$ for every $j \le k$.

3. $a_{k+1} = a_k + 2a_{k-1} = 2^k + (-1)^k + 2\big(2^{k-1} + (-1)^{k-1}\big) = 2^{k+1} + (-1)^{k-1}\big(-1 + 2\big)$

4. $= 2^{k+1} + (-1)^{k-1} = 2^{k+1} + (-1)^{k+1}$ ✓ (check: $a_3 = 7,\ a_4 = 17,\ a_5 = 31$)

True for all $n \ge 1$. The same idea proves bounds on Fibonacci numbers and the closed forms of second-order difference equations used in digital control.