Mathematical Induction: How to Prove by Induction (with Examples)

The three steps

1. Base case. Prove P(n₀) for the first value n₀, usually 0 or 1.
2. Inductive hypothesis. Assume P(k) is true for some arbitrary k ≥ n₀.
3. Inductive step. Using the hypothesis, prove P(k + 1).

Then conclude: by the principle of mathematical induction, P(n) is true for all n ≥ n₀.

Example 1: the sum of the first n odd numbers

Claim: 1 + 3 + 5 + … + (2n − 1) = n² for all n ≥ 1.

1. Base case: for n = 1 the left side is 1 and the right side is 1² = 1.
2. Hypothesis: assume 1 + 3 + … + (2k − 1) = k².
3. Step: 1 + 3 + … + (2k − 1) + (2k + 1) = k² + (2k + 1) = (k + 1)².

The statement holds for k + 1, so it holds for every n ≥ 1.

Example 2: an inequality that starts later

Claim: 2ⁿ ≥ n² for all n ≥ 4. (It fails at n = 3, since 8 < 9, which is why the base case is 4. Induction can start at any value.)

1. Base case: for n = 4, 2⁴ = 16 and 4² = 16, so 16 ≥ 16.
2. Hypothesis: assume 2ᵏ ≥ k² for some k ≥ 4.
3. Step: 2ᵏ⁺¹ = 2·2ᵏ ≥ 2k². It is enough to show 2k² ≥ (k + 1)². Now 2k² − (k + 1)² = k² − 2k − 1, which is at least 7 for k ≥ 4, so it is positive.

Therefore 2ᵏ⁺¹ ≥ (k + 1)², and the claim holds for all n ≥ 4.

Example 3: divisibility

Claim: 6 divides n³ − n for every integer n ≥ 1.

1. Base case: for n = 1, n³ − n = 0, which 6 divides.
2. Hypothesis: assume 6 divides k³ − k.
3. Step: (k + 1)³ − (k + 1) = (k³ − k) + 3k(k + 1). The first part is divisible by 6 by the hypothesis. In the second, k(k + 1) is a product of consecutive integers, hence even, so 3k(k + 1) is divisible by 6.

Both parts are divisible by 6, so the sum is, and the claim holds for all n ≥ 1.

Strong induction

In strong induction the hypothesis is that P(j) is true for every j from the starting value up to k. It is useful when the next case depends on more than the previous one, as with the Fibonacci numbers.

Claim: Fₙ < 2ⁿ for all n ≥ 1, where F₁ = F₂ = 1 and Fₙ = Fₙ₋₁ + Fₙ₋₂. Base cases: F₁ = 1 < 2 and F₂ = 1 < 4. Step: for k ≥ 2, Fₖ₊₁ = Fₖ + Fₖ₋₁ < 2ᵏ + 2ᵏ⁻¹ < 2ᵏ + 2ᵏ = 2ᵏ⁺¹. Two base cases are needed because the step uses the two previous values.

A write-up template

Claim: P(n) for all n ≥ n₀. Proof by induction on n. Base case: show P(n₀). Inductive step: let k ≥ n₀ and assume P(k). Show P(k + 1), stating clearly where the hypothesis is used. By the principle of mathematical induction, P(n) holds for all n ≥ n₀.

Common mistakes

• Leaving out the base case, or checking one that is not the first case of the claim.
• Assuming what you want to prove: the hypothesis is P(k), never P(k + 1).
• Never using the hypothesis in the step. If it is not used, the argument is not induction.
• Starting at the wrong value, such as proving 2ⁿ ≥ n² from n = 1 or n = 3.
• Using ordinary induction when the step needs more than the previous case (use strong induction and enough base cases).