Mathematical Induction: Proving Statements for Every Positive Integer

The big question

Look at this pattern:

• 1 = 1
• 1 + 2 = 3
• 1 + 2 + 3 = 6
• 1 + 2 + 3 + 4 = 10
• 1 + 2 + 3 + 4 + 5 = 15

It seems that 1 + 2 + 3 + … + n = n(n + 1)/2. We can check n = 1, 2, 3 or even 100, but we can never check every positive integer one by one. Mathematical induction is the tool that proves a statement for all of them at once.

The domino idea

Imagine a long line of dominoes. You do not need to push every one. You only need to know two things:

1. The first domino falls.
2. Whenever one domino falls, it knocks over the next one.

Then 1 → 2 → 3 → 4 → … and every domino falls. Induction works the same way.

What is P(n)?

P(n) is the statement we want to prove, written in terms of n. For example:

P(n): 1 + 2 + 3 + … + n = n(n + 1)/2

• P(1) means the statement with n = 1.
• P(k) means the statement with n = k.
• P(k + 1) means the statement with every n replaced by k + 1.

The four steps of a proof

1. Base case: show P(1) is true (left-hand side = right-hand side).
2. Inductive hypothesis: assume P(k) is true for some positive integer k.
3. Inductive step: use that assumption to prove P(k + 1).
4. Conclusion: since P(1) is true and P(k) ⇒ P(k + 1), P(n) is true for all positive integers n.

Proof 1: the sum of the first n integers

The key move is to add the next term, (k + 1), to both sides of the hypothesis, then factorise rather than expand everything.

Proof 2: the sum of the first n odd numbers

Note that the next odd number after (2k − 1) is (2(k + 1) − 1) = 2k + 1.

Proof 3: the sum of squares

Proof 4: divisibility

For divisibility, write the hypothesis as an equation: "5^k − 1 = 4m for some integer m".

Why both steps matter

• No base case: the statement "n + 1 = n" passes the inductive step (adding 1 to both sides of k + 1 = k gives k + 2 = k + 1), yet it is false for every n. The first domino never falls.
• No inductive step: checking n = 1, 2, 3 is only evidence. A pattern can work for many values and then fail.

Common mistakes

1. Assuming P(k + 1) instead of proving it.
2. Writing P(k + 1) wrongly: replace every n with k + 1, including inside brackets.
3. Forgetting to add the (k + 1)th term to the series.
4. Expanding everything instead of taking out the common factor (k + 1).
5. Leaving out the conclusion sentence: WAEC awards a mark for it.

Practice

1. Prove that 2 + 4 + 6 + … + 2n = n(n + 1).
2. Prove that 6ⁿ − 1 is divisible by 5 for all positive integers n.
3. Write down P(k + 1) for P(n): 1 + 4 + 7 + … + (3n − 2) = n(3n − 1)/2.
4. Prove the statement in question 3.

Answers: 1. Base: 2 = 1(2). Step: k(k + 1) + 2(k + 1) = (k + 1)(k + 2) · 2. Base: 6 − 1 = 5. Step: if 6^k = 5m + 1, then 6^{k + 1} − 1 = 6(5m + 1) − 1 = 30m + 5 = 5(6m + 1) · 3. 1 + 4 + … + (3k − 2) + (3k + 1) = (k + 1)(3k + 2)/2 · 4. Base: 1 = 1(2)/2. Step: k(3k − 1)/2 + (3k + 1) = (3k² + 5k + 2)/2 = (k + 1)(3k + 2)/2

Next class: Differentiation from First Principles.