Divisibility example

Claim: If $n$ is a positive integer, then $6^{n} - 1$ is divisible by 5. We will refer to this claim as $P(n)$.

Try it out

Before proving $P(n)$ with mathematical induction, let’s see if the property holds for some sample values. When $n = 3$ we have that $6^{3} - 1 = 216 - 1 = 215$. Since $215$ ends with a 5, it is clearly divisible by 5.

As another test, suppose $n = 5$. We have that $6^{5} - 1 = 7776 - 1 = 7775$, which is also divisible by 5.

Induction proof

We wish to use mathematical induction to prove that $P(n)$ holds for all positive integers $n$. That is, that $6^{n} - 1$ is divisible by 5.

Base case

We must prove that $P(n)$ holds for the smallest positive integer, $n = 1$, that is, that $6^{1} - 1$ is divisible by 5. We have that $6^{1} - 1 = 6 - 1 = 5$ is divisible by 5, so $P(1)$ is true. The base case holds.

Inductive step

We assume the inductive hypothesis - that $P(k)$ holds for some arbitrary positive integer $k$. In other words, we assume that $6^{k} - 1$ is divisible by 5 for our arbitrary $k$. We must prove that $P(k+1)$ also holds – i.e., that $6^{k+1} - 1$ is also divisible by 5. We have that:

Since $6^{k} - 1$ is divisible by 5 from our inductive hypothesis, any multiple of it is also divisible by 5. Thus, $6(6^{k} - 1)$ is divisible by 5. Adding 5 to a number that is a multiple of 5 yields another multiple of 5. Thus $6(6^{k} - 1) + 5$ is divisible by 5, we have proved $P(k+1)$. The inductive step holds.

We conclude that for all positive integers $n$, $P(n)$ holds – that is, that $6^{n} - 1$ is divisible by 5.