Anand Sir ยท Learn with understanding

Proof by induction: a worked example for IB Maths AA HL

Learn the base case, induction hypothesis and inductive step with an original sum-of-odd-numbers proof, common mistakes and a practice problem.

A pattern can suggest a result, but checking a few cases does not prove it for every positive integer. Induction proves a starting case and a rule that carries the result from one integer to the next.

This original teaching example practises proof structure. It is not an IB past-paper question.

Problem: sum the first n odd numbers

Prove that, for every integer n โ‰ฅ 1:

1 + 3 + 5 + โ‹ฏ + (2n โˆ’ 1) = nยฒ.

For n = 1, 2 and 3 the sums are 1, 4 and 9. These cases help us notice the square-number pattern. The proof still needs to cover all positive integers.

Write the proof in three stages

1. Check the base case

When n = 1, the left side is 1 and the right side is 1ยฒ = 1. The statement holds for n = 1.

2. State the induction hypothesis

Assume that, for an arbitrary integer k โ‰ฅ 1:

1 + 3 + โ‹ฏ + (2k โˆ’ 1) = kยฒ.

This is a temporary assumption for the conditional step. We have not assumed the result for k + 1.

3. Prove the next case using that assumption

The next odd number is 2(k + 1) โˆ’ 1 = 2k + 1. Add it to the sum covered by the hypothesis:

1 + 3 + โ‹ฏ + (2k โˆ’ 1) + (2k + 1)
= kยฒ + 2k + 1
= (k + 1)ยฒ.

So if the statement holds for k, it holds for k + 1. Together with the base case, this proves the result for every integer n โ‰ฅ 1 by mathematical induction.

Why the two parts work together

The base case gives us the result for 1. The conditional step then gives it for 2, then 3, and so on. A starting case without the step proves only one case; a step without a starting case does not establish where the chain begins.

Common mistakes to check in your working

  • Adding 2k โˆ’ 1 again: that term is already in the assumed sum. The next term is 2k + 1.
  • Starting with the desired answer: write the sum for k + 1, substitute the hypothesis, then simplify to (k + 1)ยฒ.
  • Skipping the domain: specify positive integers and the starting value.
  • Only testing examples: numerical checks are useful for spotting errors but do not establish the inductive step.

Try it yourself: a different sum

Prove that 2 + 4 + โ‹ฏ + 2n = n(n + 1) for every integer n โ‰ฅ 1. Identify the next term before doing any algebra.

Show the worked solution

Base: n = 1 gives 2 = 1 ร— 2.

Assumption: suppose 2 + 4 + โ‹ฏ + 2k = k(k + 1) for an arbitrary integer k โ‰ฅ 1.

Step: add 2(k + 1) to obtain k(k + 1) + 2(k + 1) = (k + 1)(k + 2), the required expression for n = k + 1.

Therefore the result holds for all integers n โ‰ฅ 1 by induction.

Next, explain aloud exactly where you used the induction hypothesis. If that step feels unclear, bring your attempt to an IB Maths AA HL lesson.