Lesson 4: Proving divisibility by induction

Prove 7n−17^n - 1 is divisible by 66

SkillsProving divisibility by inductionStructure of an induction proof

Worked example

  • Simple familiar
  • Technology free

Prove by mathematical induction that 7n−17^n - 1 is divisible by 66 for all n∈Z+n \in \mathbb{Z}^+.

1 of 6 steps
  1. Step 1: Initial statement

    Let P(n)P(n) be the statement "7n−17^n - 1 is divisible by 66", n∈Z+n \in \mathbb{Z}^+. When n=1n = 1: 71−1=6=6×17^1 - 1 = 6 = 6 \times 1. So P(1)P(1) is true.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Write the assumption as an equation, f(k)=mMf(k) = mM with M∈ZM \in \mathbb{Z}.

  2. Use index laws to write f(k+1)f(k+1) in terms of the power in f(k)f(k).

  3. Substitute the assumption.

  4. Factor out mm and say why the other factor is an integer.

Watch out for

  • Writing the assumption as 7k−1=6k7^k - 1 = 6k. The multiplier is an unknown integer MM, not kk.

  • Stopping at 42M+642M + 6 without factoring out 66 and saying that the bracket is an integer.

Save your progress with a free account