Induction: Structure Explained with Worked Examples

Proof by induction shows a statement holds for every positive integer by proving two things: the base case is true, and whenever is true then is also true.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Induction: structure means

Think of dominoes. The base case knocks over the first one, and the inductive step guarantees that each falling domino knocks over the next. Together they show that every domino falls. You must always prove both parts: a true base case with a broken step proves nothing, and vice versa.

In the inductive step you assume (the inductive hypothesis) and use it to prove . For sums, add the next term, as in the sum of r(r+1) and the sum of 1 over r(r+1). For matrices, multiply by one more copy, as in the powers of a shear matrix. A sum with factorials is handled in the sum of r times r factorial.

Divisibility results are proved by writing the expression in terms of the expression, as in divisibility by induction. Compare this with proof by contradiction, which suits negative statements. Finite sums are also covered in standard sigma results.

What is it used for?

Induction proves a statement for every positive integer by proving it for the first one and then showing that each case leads to the next.

How to use induction: structure

  1. Basis: check that the statement is true for (or the first value required).
  2. Assumption: suppose it is true for .
  3. Step: show that it is then true for , using the assumption.
  4. Conclusion: state "true for , and if true for then true for , so true for all positive integers ".

Graph

Triangular numbers 1, 3, 6, 10, 15 follow n(n+1)/23 × 4 ÷ 2 = 65 × 6 ÷ 2 = 1501234560246810121416Triangular numbers 1, 3, 6, 10, 15 follow n(n+1)/2xyGraph with x from 0 to 6 and y from 0 to 17. Shows bars (5); point 3 × 4 ÷ 2 = 6 at (3, 6); point 5 × 6 ÷ 2 = 15 at (5, 15).

Each bar is the previous bar plus the next integer, which is exactly the inductive step.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: sum of the first n integers

Prove .

Worked example
Answer
12n(n+1)\tfrac12n(n+1)
  1. Base case n = 1
  2. Assume true for n = k
  3. Add the next term
  4. This is the formula with n = k + 1

Example 2: an inequality

Prove for all positive integers .

Worked example
Answer
2n>n2^{n}>n
  1. Base case n = 1
  2. Assume
  3. Then

Example 3: a divisibility result

Prove that is divisible by 7.

Worked example
Answer
7∣11n−4n7\mid11^{n}-4^{n}
  1. Base case n = 1
  2. Assume
  3. Then
  4. Both terms are multiples of 7

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

P(n): Σr = n(n + 1)/2, base n = 1

LHS = 1, RHS = 1

1.

Step for k = 4

10 + 5

15.

Target P(5)

5·6/2

15.

Algebra

k(k+1)/2 + (k+1) = (k+1)(k+2)/2

k = 4: 15.

Word problems

Induction: show P(1) (base case); then assume P(k) and prove P(k + 1). Conclude P(n) for all n ≥ 1.

Base case

n = 1: n(n + 1)/2.

  1. 1·2/2
  2. Check: ✓1

Inductive step

Assume P(4): 10. Add the next term 5.

  1. 10 + 5
  2. Check: ✓15

Target Higher

P(5) right side.

  1. 5·6/2
  2. Check: equal ✓15

General step Higher

k(k+1)/2 + (k+1) at k = 4.

  1. (k+1)(k+2)/2
  2. Check: 15 ✓15

Common mistakes

Skipping the base case

only the step ✗

both parts ✓

Needed.

Assuming P(k + 1)

circular ✗

assume P(k) ✓

Hypothesis.

No conclusion

stop ✗

state “true for all n ≥ 1” ✓

Final line.

Wrong target

P(k) ✗

P(k + 1) ✓

Prove the next case.

Exam tips

  1. Base case.
  2. Assume P(k).
  3. Prove P(k + 1).
  4. Conclude for all n.
  5. Use the hypothesis explicitly.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. P(1) for Σr = n(n+1)/2 Foundation

1

2. P(3) right side Foundation

6

3. Step k = 5: 15 + 6 Foundation

21

4. P(6) right side Higher

21

5. P(10) right side Higher

55

6. Σ r for r = 1..4 Higher

10

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Mathematical induction
Proof over the integers.
Base case
P(1).
Inductive hypothesis
P(k) assumed.
Inductive step
P(k) ⇒ P(k + 1).
Conclusion
True for all n.
Domino principle
Why it works.

Frequently asked questions

What are the steps of induction?

Base case, inductive step, conclusion.

What do I assume?

P(k) is true for some k.

What must I prove?

P(k + 1).

Do I need a base case?

Yes.

Which page covers the sum of r(r+1)?

induction: Σr(r+1).

Which page covers proof by contradiction?

proof by contradiction.

More in Further pure maths and the formula sheets.