Proving Divisibility Results by Induction

A second broad family of statements provable by induction asserts that some expression built from $n$ is always divisible by a fixed integer, for every natural number $n$. The key algebraic device is to write the $(k+1)$-th case as the $k$-th case plus (or times) an adjustment, so that the divisibility of the $k$-th case (from the inductive hypothesis) can be factored out of the whole expression.

The general pattern. To prove that $g(n)$ is divisible by $d$, by induction: (i) verify $g(1)$ is divisible by $d$; (ii) assume $g(k) = d\cdot m$ for some integer $m$ (the inductive hypothesis); (iii) express $g(k+1)$ in terms of $g(k)$ -- typically as $g(k+1) = g(k) + (\text{something visibly divisible by } d)$, or as $g(k+1) = c\cdot g(k) + (\text{something visibly divisible by } d)$ for a constant $c$ -- and conclude $g(k+1)$ is a multiple of $d$.

Worked example. We prove, in full, that $n^3 - n$ is divisible by $6$ for every natural number $n$.

Proof. Let $P(n)$ denote the statement that $n^3 - n$ is divisible by $6$.

Base case. For $n=1$: $1^3 - 1 = 0$, and $0 = 6 \times 0$ is divisible by $6$. So $P(1)$ is true.

Inductive step. Assume $P(k)$ is true for some $k \ge 1$, i.e. $k^3 - k = 6m$ for some integer $m$. We must show $(k+1)^3-(k+1)$ is also divisible by $6$. Expanding:

By the inductive hypothesis, $k^3-k = 6m$. Also, $k(k+1)$ is a product of two consecutive integers, so one of them is always even, which means $k(k+1)$ is always even -- write $k(k+1) = 2t$ for some integer $t$. Substituting both:

Since $m+t$ is an integer, $(k+1)^3-(k+1)$ is divisible by $6$, so $P(k+1)$ is true.

Since $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ for every $k \ge 1$, $P(n)$ is true for every $n \ge 1$: $n^3-n$ is divisible by $6$ for every natural number $n$. $\blacksquare$ …