• Practice
  • About 20 min
  • 5 practice questions

The principle of mathematical induction

Prove statements about every natural number by the initial step and the inductive step, for sums, divisibility and inequalities, and see why both steps are needed.

If something looks wrong, please tell us.

By the end of this lesson you can

  • State the principle of mathematical induction and its two steps.
  • Prove formulas for sums of series by induction.
  • Prove divisibility results and inequalities by induction, starting from a suitable first value.
  • Explain why checking many cases is not a proof, and why both steps are essential.

Add the first few odd numbers: 1 = 1, 1 + 3 = 4, 1 + 3 + 5 = 9, 1 + 3 + 5 + 7 = 16. The answers are squares, so we guess that 1 + 3 + 5 + ... + (2n − 1) = n². A guess, or conjecture, is not a proof: we cannot check infinitely many values of n. Mathematical induction proves such statements for every natural number in two steps.

The principle

Think of climbing an endless staircase. You can reach every step if (a) you can climb the first step, and (b) from any step you can climb to the next. For a statement P(n) about natural numbers n:

  1. Initial step: show that P(1) is true.
  2. Inductive step: assume P(k) is true for some natural number k (the induction hypothesis) and use it to show that P(k + 1) is true.
  3. Conclusion: then P(n) is true for every natural number n.

How induction reaches every n

  1. P(1) is checked directly The initial step.
  2. P(1) ⇒ P(2) The inductive step with k = 1.
  3. P(2) ⇒ P(3) The same step with k = 2.
  4. ... and so on for ever Each true statement passes truth to the next, so every P(n) is true.

Worked example 1: a sum

Prove 1 + 4 + 7 + ... + (3n − 2) = n(3n − 1)/2 for all n ∈ N. Initial step: for n = 1 the left side is 1 and the right side is 1 × 2/2 = 1, so P(1) is true. Inductive step: assume 1 + 4 + ... + (3k − 2) = k(3k − 1)/2. The next term is 3(k + 1) − 2 = 3k + 1. Then 1 + 4 + ... + (3k − 2) + (3k + 1) = k(3k − 1)/2 + (3k + 1) = (3k² − k + 6k + 2)/2 = (3k² + 5k + 2)/2 = (k + 1)(3k + 2)/2. Since 3k + 2 = 3(k + 1) − 1, this is (k + 1)(3(k + 1) − 1)/2, which is P(k + 1). Conclusion: by the principle of mathematical induction, P(n) is true for all n ∈ N.

The same plan proves the standard results 1 + 2 + ... + n = n(n + 1)/2 and 1² + 2² + ... + n² = n(n + 1)(2n + 1)/6. In the second, the inductive step needs k(k + 1)(2k + 1)/6 + (k + 1)² = (k + 1)(2k² + 7k + 6)/6 = (k + 1)(k + 2)(2k + 3)/6, which is the formula with n = k + 1.

Worked example 2: a sum of fractions

Prove 1/(1 × 3) + 1/(3 × 5) + ... + 1/((2n − 1)(2n + 1)) = n/(2n + 1). Initial step: 1/(1 × 3) = 1/3 and 1/(2 + 1) = 1/3. Inductive step: assume the sum up to k terms is k/(2k + 1). Adding the (k + 1)-th term 1/((2k + 1)(2k + 3)): k/(2k + 1) + 1/((2k + 1)(2k + 3)) = [k(2k + 3) + 1]/((2k + 1)(2k + 3)) = (2k² + 3k + 1)/((2k + 1)(2k + 3)) = (2k + 1)(k + 1)/((2k + 1)(2k + 3)) = (k + 1)/(2k + 3) = (k + 1)/(2(k + 1) + 1). So P(k + 1) holds, and the result is true for all n ∈ N.

Divisibility

For a divisibility statement, write the induction hypothesis as an equation, for example expression = 9m for some integer m, solve it for the highest power, and substitute into the expression for k + 1.

Worked example 3: divisible by 9

Prove that 4ⁿ + 15n − 1 is divisible by 9 for all n ∈ N. Initial step: n = 1 gives 4 + 15 − 1 = 18 = 9 × 2. Inductive step: assume 4ᵏ + 15k − 1 = 9m for an integer m, so 4ᵏ = 9m − 15k + 1. Then 4ᵏ⁺¹ + 15(k + 1) − 1 = 4 × 4ᵏ + 15k + 14 = 4(9m − 15k + 1) + 15k + 14 = 36m − 60k + 4 + 15k + 14 = 36m − 45k + 18 = 9(4m − 5k + 2), which is a multiple of 9. Hence the statement is true for all n ∈ N.

In the same way one proves that aⁿ − bⁿ is divisible by a − b: write aᵏ⁺¹ − bᵏ⁺¹ = a(aᵏ − bᵏ) + bᵏ(a − b), and both parts are multiples of a − b.

Inequalities and other starting values

Induction can start at any integer n₀ instead of 1: prove P(n₀), then P(k) ⇒ P(k + 1) for k ≥ n₀, and the statement holds for all n ≥ n₀.

Worked example 4: 2ⁿ > n² for n ≥ 5

First test small values: n = 2 gives 4 = 4, n = 3 gives 8 < 9, n = 4 gives 16 = 16, so the inequality fails there, and we start at n = 5. Initial step: 2⁵ = 32 > 25 = 5². Inductive step: assume 2ᵏ > k² for some k ≥ 5. Then 2ᵏ⁺¹ = 2 × 2ᵏ > 2k². Now 2k² − (k + 1)² = k² − 2k − 1 = (k − 1)² − 2, which is positive because k − 1 ≥ 4. So 2k² > (k + 1)², and therefore 2ᵏ⁺¹ > (k + 1)². The inequality holds for all n ≥ 5.

Worked example 5: a preview of De Moivre's theorem

With i² = −1, the textbook proves (cos θ + i sin θ)ⁿ = cos nθ + i sin nθ by induction, a result studied fully in Class 12. The inductive step multiplies out: (cos kθ + i sin kθ)(cos θ + i sin θ) = (cos kθ cos θ − sin kθ sin θ) + i(sin kθ cos θ + cos kθ sin θ) = cos(k + 1)θ + i sin(k + 1)θ, using the compound-angle formulas. Induction is also used in the textbook to prove sums of cosines of angles in arithmetic progression.

Why both steps are needed

  • Checking cases is not enough. n² − n + 41 is prime for n = 1, 2, ..., 40, but for n = 41 it equals 41² − 41 + 41 = 41², which is not prime.
  • The inductive step alone is not enough. Take the false claim n² + n + 1 is even. If k² + k + 1 is even, then (k + 1)² + (k + 1) + 1 = (k² + k + 1) + 2(k + 1) is even too, so the step works. But P(1) is 3, which is odd, so the chain never starts.

Prove P(1) (or P(n₀)). Assume P(k), prove P(k + 1). Then P(n) is true for every n from the starting value on.

— The principle of mathematical induction

Key takeaways: write P(n) clearly, check the first value, and in the inductive step use the hypothesis P(k) openly; add the next term for a sum, substitute for the highest power in a divisibility proof, and compare carefully in an inequality. State the conclusion at the end.

Check your understanding

  1. 1. In the inductive step of a proof by mathematical induction, what must be shown?

    1. P(k) is true for every k
    2. P(1) is true
    3. If P(k) is true, then P(k + 1) is true
    4. P(k + 1) is true without using P(k)
    Show answer

    Answer: C. The inductive step assumes P(k) (the induction hypothesis) and shows it forces P(k + 1). Checking P(1) is the initial step, and assuming P(k) for every k would assume what is to be proved.

  2. 2. The statement 2ⁿ > n² is true for n = 1 but false for n = 2, 3 and 4. From which value should an induction proof start so that the statement is proved for every n from there on?

    1. n = 1
    2. n = 2
    3. n = 5
    4. n = 4
    Show answer

    Answer: C. 2⁵ = 32 > 25, and for k ≥ 5 the inductive step works because 2k² > (k + 1)². Starting at 1 fails because the chain breaks at n = 2 (4 is not greater than 4).

  3. 3. In proving 1 + 2 + ... + n = n(n + 1)/2, what is added to k(k + 1)/2 to obtain the sum for n = k + 1?

    1. k
    2. k + 1
    3. k + 2
    4. 2k + 1
    Show answer

    Answer: B. The sum up to k + 1 is the sum up to k plus the next term, k + 1. Then k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, as required.

  4. 4. By which number is 5ⁿ − 1 divisible for every natural number n?

    1. 3
    2. 6
    3. 5
    4. 4
    Show answer

    Answer: D. For n = 1, 5 − 1 = 4. If 5ᵏ − 1 = 4m, then 5ᵏ⁺¹ − 1 = 5(4m + 1) − 1 = 20m + 4 = 4(5m + 1). So 4 divides it for all n. (For n = 1 the value 4 is not divisible by 3, 6 or 5.)

  5. 5. For the claim 'n² + n + 1 is even', the inductive step P(k) ⇒ P(k + 1) can be carried out. Why is the claim still not proved?

    1. Because P(1) = 3 is odd, so the initial step fails
    2. Because the inductive step needs k ≥ 2
    3. Because induction cannot prove statements about even numbers
    4. Because the claim is true only for even n
    Show answer

    Answer: A. Induction needs both steps. Here P(1) gives 1 + 1 + 1 = 3, which is odd, so there is no first true statement to pass on. In fact n² + n + 1 = n(n + 1) + 1 is always odd.

Privacy · Terms · Refunds · Delivery