Induction

Prove statements about all positive integers.

Mathematical induction is a proof technique for statements numbered by integers: P(1), P(2), P(3), and so on. It lets us prove infinitely many statements with a finite argument.

Learning objectives

After this lesson you should be able to:

  • identify the statement P(n);
  • prove a base case;
  • state the induction hypothesis;
  • prove the induction step;
  • explain the domino-chain intuition;
  • avoid common proof gaps.

Domino intuition

Imagine infinitely many dominoes in a line.

  1. The base case knocks over the first domino.
  2. The induction step proves that whenever one domino falls, the next one falls.

Together, these prove that every domino falls.

A basic induction proof has this structure:

  1. Prove P(1) or another starting case.
  2. Assume P(k) for an arbitrary integer k in the range.
  3. Use that assumption to prove P(k+1).
  4. Conclude P(n) is true for all integers in the range.

Base case

The base case proves the first statement directly. If the theorem starts at n=1, prove P(1). If it starts at n=0, prove P(0).

Induction hypothesis

The induction hypothesis is the temporary assumption that P(k) is true. You do not assume the final result for every n. You assume one arbitrary case so you can prove the next case.

Induction step

The induction step proves

P(k) -> P(k+1)

This is the part that makes the chain continue.

Worked example 1: sum formula

Prove

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

for all positive integers n.

Base case: when n=1, the left side is 1 and the right side is 1(2)/2 = 1. The base case is true.

Induction hypothesis: assume for some k >= 1 that

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

Induction step: prove the formula for k+1.

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

That is exactly the formula with n=k+1. Therefore the statement is true for all positive integers.

Worked example 2: divisibility

Prove that 3 divides 4^n - 1 for all n >= 1.

Base case: when n=1, 4^1 - 1 = 3, which is divisible by 3.

Induction hypothesis: assume 4^k - 1 is divisible by 3. That means 4^k - 1 = 3m for some integer m.

Induction step:

4^(k+1) - 1 = 4*4^k - 1
            = 4(4^k - 1) + 3
            = 4(3m) + 3
            = 3(4m + 1)

So 4^(k+1)-1 is divisible by 3.

Common pitfalls

  • Checking examples and calling it a proof.
  • Forgetting the base case.
  • Assuming P(k+1) instead of proving it.
  • Not using the induction hypothesis.
  • Confusing k and k+1.
  • Writing algebra without explaining the proof structure.

Practice

  1. What is the base case for a theorem beginning “for all n >= 0”?
  2. In an induction proof, what do you assume temporarily?
  3. What must the induction step prove?
  4. For the sum formula above, where was the induction hypothesis used?
  5. Why are examples alone not enough for a proof about all integers?
  1. Usually n=0.
  2. Assume P(k) for an arbitrary k in the allowed range.
  3. It must prove P(k+1) from P(k).
  4. In replacing 1+2+...+k with k(k+1)/2.
  5. Examples check only finitely many cases; the theorem claims infinitely many.

Subtopic guided practice and checkpoints

Induction is a proof template, not a calculation trick. The goal is to show that truth starts and then passes from one case to the next.

Lab 1: name the statement P(n)

Guess first. In “prove 1 + 2 + ... + n = n(n+1)/2,” what is P(n)?

Guided exercise.

P(n) is the whole statement depending on n:

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

You do not prove a number; you prove a statement about every allowed n.

Checkpoint. Write P(n) for the claim “2^n >= n + 1 for all n >= 1.”

Lab 2: prove the base case

Guess first. If a theorem begins at n = 1, which case is checked first?

Guided exercise.

For the sum formula:

left side at n=1:  1
right side at n=1: 1(1+1)/2 = 1

Both sides match, so the base case is true.

Checkpoint. Prove the base case for 2^n >= n + 1 when n = 1.

Lab 3: use the induction hypothesis

Guess first. During the induction step, are you allowed to assume P(k+1)?

Guided exercise.

You assume P(k) temporarily:

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

Then you add the next term (k+1) to build the k+1 case. You are not allowed to assume the thing you are trying to prove.

Checkpoint. In a proof about 4^n - 1 being divisible by 3, write the induction hypothesis in the form 4^k - 1 = 3m for some integer m.

Lab 4: complete the induction step

Guess first. Why does adding (k+1) help prove the sum formula?

Guided exercise.

Start from the k+1 left side and use the induction hypothesis on the first k terms:

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

This is the formula with n = k+1, so truth passes to the next case.

Checkpoint. Complete the induction step for the claim 1 + 3 + 5 + ... + (2n - 1) = n^2.

  1. P(n) is the statement 2^n >= n + 1.
  2. At n = 1, 2^1 = 2 and 1 + 1 = 2, so the base case is true.
  3. The induction hypothesis can be written as 4^k - 1 = 3m for some integer m.
  4. Assume 1 + 3 + ... + (2k - 1) = k^2. Then add the next odd number: k^2 + (2(k+1)-1) = k^2 + 2k + 1 = (k+1)^2.

Induction checkpoint

Using this lesson with edumath and SymPy

Use SymPy to check algebra in an induction step.

import sympy as sp

k = sp.Symbol("k", positive=True, integer=True)
left = k*(k + 1)/2 + (k + 1)
right = (k + 1)*(k + 2)/2
sp.simplify(left - right)

\(\displaystyle 0\)

A result of 0 confirms that the algebraic expressions match. It does not replace the proof structure.

from edumath.discrete_math import induction_step_exercise

exercise = induction_step_exercise()
exercise.prompt, exercise.expected
('What is the main structure of the induction step?',
 'assume p(k), prove p(k+1)')