Lesson 1 of 7 · 16 min

The idea of proof by induction

See why checking examples is never enough, and how an initial statement, an assumption and an inductive step together prove a statement for every positive integer.

What you will be able to do

  • Explain why checking a statement for many values of nn does not prove it.
  • Name and write the four parts of a proof by induction: initial statement, assumption statement, inductive step and conclusion.
  • Explain why a proof by induction needs both the initial statement and the inductive step.

Add up the first few odd numbers and something keeps happening:

1=1,1+3=4,1+3+5=9,1+3+5+7=16.1 = 1, \qquad 1 + 3 = 4, \qquad 1 + 3 + 5 = 9, \qquad 1 + 3 + 5 + 7 = 16.

Every total is a perfect square. Does it work for the first 100100 odd numbers? The first million? You can't check them all, because there are infinitely many positive integers. This lesson shows how to prove it anyway.

Interactive

Running totals of the odd numbers

Look down the column of running totals. What kind of numbers appear?

If the pattern continues, what is 1+3+5+⋯+191 + 3 + 5 + \cdots + 19, the sum of the first 1010 odd numbers?

History

Patterns can fool you

Euler noticed that n2+n+41n^2 + n + 41 is prime for n=0,1,2,…,39n = 0, 1, 2, \ldots, 39: forty prime values in a row. But at n=40n = 40 it gives 1600+40+41=1681=4121600 + 40 + 41 = 1681 = 41^2. Forty confirming cases proved nothing. A proof has to cover every case at once.

The initial statement knocks over the first domino. The inductive step guarantees that each falling domino knocks over the next.

Think of a row of dominoes, one for each positive integer. To be sure that every domino falls, you need two facts:

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

The first fact starts things off. The second passes the fall along the row forever. Neither is enough alone: if nobody pushes the first domino, nothing falls, and if there is a gap somewhere, the fall stops there.

Key idea

The principle of mathematical induction

Let P(n)P(n) be a statement about the positive integer nn. If

  • P(1)P(1) is true, and
  • for every positive integer kk, if P(k)P(k) is true then P(k+1)P(k+1) is true,

then P(n)P(n) is true for every n∈Z+n \in \mathbb{Z}^+.

Each odd number is an L-shaped layer. Adding the nnth odd number, 2n−12n - 1, turns an (n−1)×(n−1)(n - 1) \times (n - 1) square into an n×nn \times n square.

The picture shows why the odd numbers build squares: the next odd number wraps an L-shape around the square you already have. A proof by induction turns exactly that idea, "if it works for one square, it works for the next", into algebra.

The four parts of a proof by induction

  1. Initial statement

    Show that P(1)P(1) is true by evaluating both sides at n=1n = 1.

  2. Assumption statement

    Assume that P(k)P(k) is true for some k∈Z+k \in \mathbb{Z}^+, and write out what that means.

  3. Inductive step

    Prove that P(k+1)P(k+1) is then true. Write down the target and use the assumption to reach it.

  4. Conclusion

    State that since P(1)P(1) is true and P(k)⇒P(k+1)P(k) \Rightarrow P(k+1), by the principle of mathematical induction P(n)P(n) is true for all n∈Z+n \in \mathbb{Z}^+.

Interactive

Prove the odd-number pattern

Step through each part. The table checks the first few values of nn, but only the four parts together prove the statement for every nn.

Worked example

Prove 1+2+4+⋯+2n−1=2n−11 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1

  • Simple familiar
  • Technology free

Prove by mathematical induction that

1+2+4+⋯+2n−1=2n−11 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1

for all n∈Z+n \in \mathbb{Z}^+.

6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Define P(n)P(n) and check P(1)P(1) by evaluating both sides.

  2. Assume P(k)P(k) for some k∈Z+k \in \mathbb{Z}^+.

  3. Write the target P(k+1)P(k+1), including the new last term.

  4. Replace the first kk terms using the assumption, then simplify to the target.

  5. Write the conclusion.

Watch out for

  • Writing the new term as 2k+12^{k+1}. The last term of the sum to k+1k + 1 terms is 2(k+1)−1=2k2^{(k+1) - 1} = 2^k.

  • Writing 2k+2k=4k2^k + 2^k = 4^k or 22k2^{2k}. In fact 2k+2k=2×2k=2k+12^k + 2^k = 2 \times 2^k = 2^{k+1}.

Put the lines of this proof that 2+4+6+⋯+2n=n(n+1)2 + 4 + 6 + \cdots + 2n = n(n + 1) for all n∈Z+n \in \mathbb{Z}^+ in order.

Drag the handles, or use the arrow buttons, to put these in order.

  1. =(k+1)(k+2)= (k + 1)(k + 2), which is the right-hand side of P(k+1)P(k + 1), so P(k+1)P(k + 1) is true.
  2. When n=1n = 1: LHS =2= 2 and RHS =1(2)=2= 1(2) = 2, so P(1)P(1) is true.
  3. Then 2+4+⋯+2k+2(k+1)=k(k+1)+2(k+1)2 + 4 + \cdots + 2k + 2(k + 1) = k(k + 1) + 2(k + 1), using the assumption.
  4. Assume P(k)P(k) is true for some k∈Z+k \in \mathbb{Z}^+: 2+4+⋯+2k=k(k+1)2 + 4 + \cdots + 2k = k(k + 1).
  5. Since P(1)P(1) is true and P(k)⇒P(k+1)P(k) \Rightarrow P(k + 1), P(n)P(n) is true for all n∈Z+n \in \mathbb{Z}^+ by mathematical induction.

Here is why the initial statement matters. Consider the claim

2+4+6+⋯+2n=n2+n+1.2 + 4 + 6 + \cdots + 2n = n^2 + n + 1.

Suppose it is true for n=kn = k. Adding the next term, 2(k+1)2(k + 1), gives

2+4+⋯+2k+2(k+1)=k2+k+1+2k+2=k2+3k+3=(k+1)2+(k+1)+1,2 + 4 + \cdots + 2k + 2(k + 1) = k^2 + k + 1 + 2k + 2 = k^2 + 3k + 3 = (k + 1)^2 + (k + 1) + 1,

which is the claim for n=k+1n = k + 1. The inductive step works. But at n=1n = 1 the left side is 22 and the right side is 33. The first domino never falls, and in fact the claim is false for every nn: the correct total is n2+nn^2 + n.

A student shows that "if P(k)P(k) is true then P(k+1)P(k+1) is true" for a statement P(n)P(n), but never checks any particular value of nn. What can you conclude?

Choose one answer

Common mistake

Assuming the thing you are proving

The assumption is about one particular value: "assume P(k)P(k) is true for some k∈Z+k \in \mathbb{Z}^+". Writing "assume P(n)P(n) is true for all nn" assumes the whole result, and the proof collapses. Use a new letter, kk, for the assumption.

Exam tip

What markers look for

QCAA solutions use the syllabus's four parts. Make each one easy to find: define P(n)P(n) and its domain, show the initial statement, write the assumption in full, show where the inductive step uses it, and finish with the conclusion sentence. A correct inductive step with no conclusion still loses a mark.

Summary

  • Checking cases, however many, is evidence, not proof.

  • Induction proves P(n)P(n) for all n∈Z+n \in \mathbb{Z}^+ from two facts: P(1)P(1) is true, and P(k)P(k) true implies P(k+1)P(k+1) true.

  • The four parts are the initial statement, the assumption statement, the inductive step and the conclusion.

  • The inductive step must use the assumption.

  • Without the initial statement, a statement can pass the inductive step and still be false for every value.

Finished the lesson?

Try the 3 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 1 of 70% read

Save your progress with a free account