Mathematical Induction – Problems with Solutions

This page presents several classical mathematical problems solved using the principle of mathematical induction. Mathematical induction is a rigorous proof technique used to show that a statement \( P(n) \) is true for all integers \( n \ge N \), where \( N \) is a fixed positive integer.

Table of Contents

The Two Steps of Mathematical Induction

Every mathematical induction proof consists of two fundamental steps:

  • Base Step: Prove that the statement \( P(N) \) is true for the initial value.
  • Induction Step: Assume the statement \( P(k) \) is true for some integer \( k \ge N \), and use this assumption to mathematically prove that \( P(k+1) \) is true.

Conclusion: Once both steps are established, the principle of mathematical induction guarantees that \( P(n) \) is true for all integers \( n \ge N \).

Solved Problems

Problem 1: Sum of the First \( n \) Positive Integers

Show Solution

Question: Use mathematical induction to prove that for all positive integers \( n \):

\[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \]

Solution

Let \( P(n) \) be the statement \( 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \).

Base Step: For \( n = 1 \), evaluate both sides:

\[ 1 = \frac{1(1+1)}{2} = 1 \]

Thus, \( P(1) \) is true.

Induction Step: Assume \( P(k) \) is true for some integer \( k \):

\[ 1 + 2 + \cdots + k = \frac{k(k+1)}{2} \]

Add the next term, \( (k+1) \), to both sides of the equation:

\[ 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) \]

Factor out \( (k+1) \):

\[ = (k+1) \left( \frac{k}{2} + 1 \right) = (k+1)\left(\frac{k + 2}{2}\right) \]

\[ = \frac{(k+1)(k+2)}{2} \]

This is exactly \( P(k+1) \). Hence, by the principle of mathematical induction, the statement is true for all positive integers \( n \).

Problem 2: Sum of the First \( n \) Squares

Show Solution

Question: Prove that for all positive integers \( n \):

\[ 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} \]

Solution

Base Step: For \( n = 1 \):

\[ 1^2 = \frac{1(1+1)(2(1)+1)}{6} = \frac{1 \cdot 2 \cdot 3}{6} = 1 \]

The base case holds true.

Induction Step: Assume the statement holds for \( k \):

\[ 1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6} \]

Add \( (k+1)^2 \) to both sides:

\[ 1^2 + 2^2 + \cdots + k^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \]

Find a common denominator and factor out \( (k+1) \):

\[ = \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} \]

\[ = \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} \]

\[ = \frac{(k+1)[2k^2 + k + 6k + 6]}{6} = \frac{(k+1)[2k^2 + 7k + 6]}{6} \]

Factor the quadratic polynomial \( 2k^2 + 7k + 6 = (k+2)(2k+3) \):

\[ = \frac{(k+1)(k+2)(2k+3)}{6} \]

This is the required formula for \( P(k+1) \). The proof is complete.

Problem 3: Sum of the First \( n \) Cubes

Show Solution

Question: Prove that for all positive integers \( n \):

\[ 1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{n^2 (n+1)^2}{4} \]

Solution

Base Step: For \( n = 1 \):

\[ 1^3 = \frac{1^2(1+1)^2}{4} = \frac{1 \cdot 4}{4} = 1 \]

The base case is true.

Induction Step: Assume the formula holds for \( k \):

\[ 1^3 + 2^3 + \cdots + k^3 = \frac{k^2 (k+1)^2}{4} \]

Add \( (k+1)^3 \) to both sides:

\[ \frac{k^2 (k+1)^2}{4} + (k+1)^3 \]

Factor out the common term \( (k+1)^2 \):

\[ = (k+1)^2 \left( \frac{k^2}{4} + (k+1) \right) \]

\[ = (k+1)^2 \left( \frac{k^2 + 4k + 4}{4} \right) \]

\[ = \frac{(k+1)^2 (k+2)^2}{4} \]

Thus, the formula holds for \( k+1 \) and is proven for all positive integers \( n \).

Problem 4: Divisibility Proof

Show Solution

Question: Prove that \( n^3 + 2n \) is divisible by 3 for all positive integers \( n \).

Solution

Base Step: For \( n = 1 \):

\[ 1^3 + 2(1) = 3 \]

3 is clearly divisible by 3.

Induction Step: Assume the statement holds for \( k \), meaning \( k^3 + 2k = 3M \) for some integer \( M \).

Check the expression for \( k+1 \):

\[ (k+1)^3 + 2(k+1) \]

Expand the terms:

\[ = (k^3 + 3k^2 + 3k + 1) + (2k + 2) \]

Rearrange to group our assumption:

\[ = (k^3 + 2k) + 3k^2 + 3k + 3 \]

\[ = 3M + 3(k^2 + k + 1) \]

\[ = 3(M + k^2 + k + 1) \]

Since the entire expression is a multiple of 3, it is divisible by 3, completing the proof.

Alternative observation: \( n^3 + 2n = n(n^2 + 2) = n(n^2 - 1 + 3) = n(n-1)(n+1) + 3n \). The first term is a product of three consecutive integers, which is always divisible by 3, and \( 3n \) is trivially divisible by 3.

Problem 5: Inequality Proof (\( 3^n \gt n^2 \))

Show Solution

Question: Prove that \( 3^n \gt n^2 \) for all integers \( n \ge 3 \).

Solution

Base Step: Test for the starting integer \( n = 3 \):

\[ 3^3 = 27 \quad \text{and} \quad 3^2 = 9 \]

Since \( 27 \gt 9 \), the base step is verified.

Induction Step: Assume the inequality holds for \( k \ge 3 \), so \( 3^k \gt k^2 \).

Examine the case for \( k+1 \):

\[ 3^{k+1} = 3 \cdot 3^k \gt 3 \cdot k^2 \]

We now need to show that \( 3k^2 \gt (k+1)^2 \). Expanding the right side gives \( k^2 + 2k + 1 \).

Since \( k \ge 3 \):

\[ 3k^2 = k^2 + 2k^2 \]

Because \( k \ge 3 \), we know that \( 2k^2 \ge 6k \gt 2k \) and \( k^2 \ge 9 \gt 1 \). Therefore, \( 2k^2 \gt 2k + 1 \).

Thus, \( 3k^2 \gt k^2 + 2k + 1 = (k+1)^2 \).

Therefore, \( 3^{k+1} \gt (k+1)^2 \), and the inequality holds for all \( n \ge 3 \).

Problem 6: Factorial Inequality

Show Solution

Question: Prove that \( n! \gt 2^n \) for all \( n \ge 4 \).

Solution

Base Step: For \( n = 4 \):

\[ 4! = 24 \quad \text{and} \quad 2^4 = 16 \]

Since \( 24 \gt 16 \), the base step holds.

Induction Step: Assume that \( k! \gt 2^k \) for some \( k \ge 4 \).

Look at the expression for \( (k+1)! \):

\[ (k+1)! = (k+1) \cdot k! \gt (k+1) \cdot 2^k \]

Because \( k \ge 4 \), it is clear that \( k+1 \ge 5 \gt 2 \). Therefore:

\[ (k+1) \cdot 2^k \gt 2 \cdot 2^k = 2^{k+1} \]

Thus, \( (k+1)! \gt 2^{k+1} \), completing the proof.

Problem 7: De Moivre's Theorem

Show Solution

Question: Prove that for all positive integers \( n \):

\[ [R(\cos t + i \sin t)]^n = R^n(\cos nt + i \sin nt) \]

Solution

Base Step: For \( n = 1 \):

\[ [R(\cos t + i \sin t)]^1 = R^1(\cos(1t) + i \sin(1t)) \]

The result clearly holds for \( n = 1 \).

Induction Step: Assume it is true for \( n = k \):

\[ [R(\cos t + i \sin t)]^k = R^k(\cos kt + i \sin kt) \]

Multiply both sides by another factor of \( R(\cos t + i \sin t) \):

\[ [R(\cos t + i \sin t)]^{k+1} = R^k(\cos kt + i \sin kt) \cdot R(\cos t + i \sin t) \]

\[ = R^{k+1} [(\cos kt \cos t - \sin kt \sin t) + i(\sin kt \cos t + \cos kt \sin t)] \]

Apply the trigonometric sum identities for cosine and sine:

\[ = R^{k+1} [\cos(kt + t) + i\sin(kt + t)] \]

\[ = R^{k+1} [\cos((k+1)t) + i\sin((k+1)t)] \]

This is exactly the formula for \( n = k+1 \), which completes the induction proof.

Problem 8: Sum of a Geometric Series

Show Solution

Question: Prove that for all positive integers \( n \) and for any real number \( r \neq 1 \):

\[ 1 + r + r^2 + \cdots + r^{n-1} = \frac{r^n - 1}{r - 1} \]

Solution

Base Step: For \( n = 1 \), the left side is \( r^0 = 1 \), and the right side is:

\[ \frac{r^1 - 1}{r - 1} = \frac{r - 1}{r - 1} = 1 \]

So \( P(1) \) holds.

Induction Step: Assume the formula holds for \( k \):

\[ 1 + r + r^2 + \cdots + r^{k-1} = \frac{r^k - 1}{r - 1} \]

Add the next term \( r^k \) to both sides:

\[ 1 + r + \cdots + r^{k-1} + r^k = \frac{r^k - 1}{r - 1} + r^k \]

Combine the fractions over a common denominator:

\[ = \frac{r^k - 1 + r^k(r - 1)}{r - 1} = \frac{r^k - 1 + r^{k+1} - r^k}{r - 1} \]

\[ = \frac{r^{k+1} - 1}{r - 1} \]

This is the required formula for \( P(k+1) \). The proof is complete.

Problem 9 (Challenging): A Fibonacci Identity

Show Solution

Question: The Fibonacci sequence is defined by \( F_1 = 1 \), \( F_2 = 1 \), and \( F_{n} = F_{n-1} + F_{n-2} \) for \( n \ge 3 \). Prove by induction that for all positive integers \( n \):

\[ F_1^2 + F_2^2 + F_3^2 + \cdots + F_n^2 = F_n \cdot F_{n+1} \]

Solution

Base Step: For \( n = 1 \):

Left side: \( F_1^2 = 1^2 = 1 \).

Right side: \( F_1 \cdot F_2 = 1 \cdot 1 = 1 \).

So \( P(1) \) is true.

Induction Step: Assume the identity holds for some \( k \ge 1 \):

\[ F_1^2 + F_2^2 + \cdots + F_k^2 = F_k \cdot F_{k+1} \]

Add \( F_{k+1}^2 \) to both sides:

\[ F_1^2 + F_2^2 + \cdots + F_k^2 + F_{k+1}^2 = F_k \cdot F_{k+1} + F_{k+1}^2 \]

Factor the right side:

\[ = F_{k+1}(F_k + F_{k+1}) \]

By the Fibonacci recurrence, \( F_k + F_{k+1} = F_{k+2} \). Thus:

\[ = F_{k+1} \cdot F_{k+2} \]

This is exactly the identity for \( n = k+1 \). Hence, by induction, the identity holds for all positive integers \( n \).

Numerical check: For \( n = 4 \): \( F_1^2 + F_2^2 + F_3^2 + F_4^2 = 1 + 1 + 4 + 9 = 15 \), and \( F_4 \cdot F_5 = 3 \cdot 5 = 15 \) ✓

Common Mistakes to Avoid

  1. Omitting the base case. Both the base step and the induction step are required. Without the base step, the induction step only proves an implication, not the truth of the statement.
  2. Assuming what you are trying to prove. The induction step must use the assumption \( P(k) \) to derive \( P(k+1) \). Writing \( P(k+1) = P(k) + \ldots \) in a way that presupposes the result is circular reasoning.
  3. Algebraic errors in the induction step. Carefully verify each algebraic manipulation, especially when factoring and combining fractions.
  4. Ignoring the domain constraint. For inequalities such as \( 3^n \gt n^2 \), the proof of the induction step relies on \( k \ge 3 \) (or \( k \ge 4 \), etc.). Failing to use the constraint can lead to invalid inequalities.
  5. Confusing \( P(k) \) with \( P(k+1) \). Keep track of which statement you are assuming and which you are proving.
  6. Forgetting to state the conclusion. End the proof by explicitly invoking the principle of mathematical induction.

Frequently Asked Questions

What is mathematical induction?

Mathematical induction is a proof technique used to show that a statement \( P(n) \) is true for all integers \( n \ge N \). It consists of two steps: the base step (prove \( P(N) \) is true) and the induction step (assume \( P(k) \) is true and use it to prove \( P(k+1) \) is true).

Why does mathematical induction work?

Mathematical induction works because the natural numbers are well-ordered. If \( P(N) \) is true and \( P(k) \) implies \( P(k+1) \) for all \( k \ge N \), then by repeatedly applying the induction step, \( P(N+1), P(N+2), P(N+3), \ldots \) are all true, covering every integer \( \ge N \).

What is the difference between the base case and the induction step?

The base case proves the statement is true for the smallest value \( N \) (e.g., \( n = 1 \)). The induction step proves that if the statement holds for an arbitrary \( k \), then it also holds for \( k+1 \). Both steps together establish the statement for all integers \( \ge N \).

Can mathematical induction be used for inequalities?

Yes. For inequality proofs, the induction step often requires bounding one side of the inequality and using the fact that the variable is sufficiently large (e.g., \( k \ge 3 \)) to justify additional inequalities.

What is strong induction?

Strong induction (also called complete induction) assumes that \( P(N), P(N+1), \ldots, P(k) \) are all true and uses this to prove \( P(k+1) \). It is logically equivalent to ordinary induction but sometimes more convenient, especially for statements like the fundamental theorem of arithmetic.

What are common mistakes when using mathematical induction?

Common mistakes include: (1) omitting the base case, (2) assuming what you are trying to prove (circular reasoning), (3) making an algebraic error in the induction step, and (4) failing to justify inequalities using the constraint on \( k \) (e.g., \( k \ge 3 \)).

More References