myLearning

Step 21 · Proofs and discrete maths topics

Prove statements about every whole number by checking a base case and showing each case implies the next, including strong induction for stubborn cases.

The induction principle

To prove P(n) for every n ≥ 1, show that P(1) is true (the base case), then show that P(k) implies P(k + 1) for every k ≥ 1 (the inductive step). Like a line of dominoes: the first falls, and each one knocks over the next.

  • Base case: check P(1).
  • Inductive hypothesis: assume P(k) for some k ≥ 1.
  • Inductive step: use it to prove P(k + 1).
  • Conclude that P(n) holds for every n ≥ 1.

Example: Divisibility

Prove that 3 divides 4ⁿ − 1 for every n ≥ 1.

  1. Base: 4 − 1 = 3.
  2. Assume 3 divides 4ᵏ − 1.
  3. Then 4ᵏ⁺¹ − 1 = 4(4ᵏ − 1) + 3, a sum of two multiples of 3.

AnswerProved for every n ≥ 1

Induction with sums

Example: Adding the first n numbers

Prove that 1 + 2 + ⋯ + n = n(n+1)2\frac{n(n + 1)}{2}.

  1. Base: n = 1 gives 1 on both sides.
  2. Assume 1 + ⋯ + k = k(k+1)2\frac{k(k + 1)}{2}.
  3. Add k + 1: k(k+1)2+(k+1)=(k+1)(k+2)2\frac{k(k + 1)}{2} + (k + 1) = \frac{(k + 1)(k + 2)}{2}, which is the formula for k + 1.

AnswerProved

Example: Odd numbers

Prove that 1 + 3 + 5 + ⋯ + (2n − 1) = n².

  1. Base: 1 = 1².
  2. Assume the sum up to 2k − 1 is k².
  3. Adding the next odd number, 2k + 1, gives k² + 2k + 1, which is (k + 1)².

AnswerProved

∑i=1ni2=n(n+1)(2n+1)6\sum_{i=1}^{n} i^{2} = \frac{n(n + 1)(2n + 1)}{6}

Strong induction

In strong induction you may assume P(1), …, P(k) all hold when proving P(k + 1). It suits statements where the case k + 1 depends on cases further back than k.

Example: Prime factors

Prove that every integer n ≥ 2 is a product of primes.

  1. Base: 2 is prime.
  2. Assume every number from 2 to k is a product of primes. If k + 1 is prime, we are done.
  3. Otherwise k + 1 = ab with 2 ≤ a, b ≤ k, and both a and b are products of primes.

AnswerSo k + 1 is a product of primes too

Example: Stamps

Prove that any postage of 12 cents or more can be made with 4- and 5-cent stamps.

  1. Base cases: 12 = 4 + 4 + 4, 13 = 4 + 4 + 5, 14 = 4 + 5 + 5 and 15 = 5 + 5 + 5.
  2. For n ≥ 16, the amount n − 4 is at least 12, so it can be made by assumption; add one 4-cent stamp.

AnswerProved for every amount from 12 cents up

Try it yourself

Work each one on paper first, then open the answer to check.

  1. What are the two parts of an induction proof?

    Show answer

    A base case and an inductive step

  2. In proving 2ⁿ > n for n ≥ 1, what is the base case?

    Show answer

    n = 1: 2 > 1

  3. Use the formula to find 1 + 2 + ⋯ + 100.

    Show answer

    5050

  4. Use 1 + 3 + ⋯ + (2n − 1) = n² to find the sum of the first 20 odd numbers.

    Show answer

    400

  5. In the step of a strong induction proof, what may you assume?

    Show answer

    That P(1), …, P(k) all hold

  6. Name an amount from 1 to 11 cents that cannot be made with 4- and 5-cent stamps.

    Show answer

    Any of 1, 2, 3, 6, 7 or 11

What next?