A1 - Induction for divisibility

Divisibility

For integers $d\ne0$ and $N$, “$N$ is divisible by $d$” means $N=dq$ for some integer $q$. The notation is $d\mid N$. In particular, zero is divisible by every nonzero integer, because $0=d\times0$.

Worked example 1: powers of five

Question. Prove by induction that $5^n-1$ is divisible by $4$ for all positive integers $n$.

Plan. Check the first power, then make $5^k-1$ appear inside the next expression.

For $n=1$, $5^1-1=4=4\times1$, so the basis holds.

Assume $5^k-1=4q$ for an arbitrary integer $k\ge1$, where $q$ is an integer. Then

Since $5q+1$ is an integer, the next expression is divisible by $4$.

Answer. The result holds at $n=1$, and truth at $k$ implies truth at $k+1$. Hence it holds for every positive integer $n$, by induction.

Check. Expanding $5(5^k-1)+4$ gives $5^{k+1}-5+4=5^{k+1}-1$. At $n=2$, the quotient is $24/4=6$, agreeing with $5q+1$ from $q=1$.

Worked example 2: powers of nine

Question. Prove by induction that $9^n-1$ is divisible by $8$ for all positive integers $n$.

Plan. Expose $9^k-1$ and show that the remaining term is also a multiple of $8$.

At $n=1$, $9^1-1=8=8\times1$.

Assume $9^k-1=8q$ for an arbitrary integer $k\ge1$, with $q$ an integer. Then

The bracket $9q+1$ is an integer.

Answer. The basis holds, and the result for $k$ implies the result for $k+1$. Therefore $9^n-1$ is divisible by $8$ for every positive integer $n$, by induction.

Check. At $n=2$, $9^2-1=80=8\times10$. The quotient recurrence gives $9(1)+1=10$, as required.

Watch out

Writing $5^k-1=4q$ without saying $q$ is an integer does not express divisibility. Any real number can be written as $4q$ with a real $q$.

Key idea

Choose the basis to match the stated domain. “All integers $n\ge2$” starts at $2$; “all nonnegative integers” starts at $0$. State the same lower bound for the arbitrary integer $k$ in the induction hypothesis.