Induction with divisibility

Proving divisibility results by mathematical induction, introducing an integer multiple for the assumption, finding a divisibility conjecture, and induction that starts at a value other than 1 or steps through odd or even integers.

Divisibility proofs

"$d$ divides $N$" means $N = dM$ for some integer $M$. In the inductive step, write the assumption this way, then rewrite the $(k + 1)$th expression so it contains the assumed one.

Example 1●●

Prove by induction that $7^n - 1$ is divisible by $6$ for all positive integers $n$.

$n = 1$: $7^1 - 1 = 6$, which is divisible by $6$.

Assume it is true for $n = k$, so $7^k - 1 = 6M$ for some integer $M$. That is, $7^k = 6M + 1$.

Prove it for $n = k + 1$: $$7^{k+1} - 1 = 7 \times 7^k - 1 = 7(6M + 1) - 1 = 42M + 6 = 6(7M + 1).$$

$7M + 1$ is an integer, so $7^{k+1} - 1$ is divisible by $6$. By induction, the result holds for all $n \ge 1$.

Example 2●●●

Prove that $5^n + 2 \times 11^n$ is divisible by $3$ for all $n \ge 1$.

$n = 1$: $5 + 22 = 27 = 3 \times 9$.

Assume $5^k + 2 \times 11^k = 3M$, so $5^k = 3M - 2 \times 11^k$.

Then $5^{k+1} + 2 \times 11^{k+1} = 5(3M - 2 \times 11^k) + 22 \times 11^k = 15M + 12 \times 11^k$.

This is $3(5M + 4 \times 11^k)$, a multiple of $3$. So by induction the result holds for all $n \ge 1$.

Finding the divisor

Example 3●

Find the largest integer that divides $3^{2n} - 1$ for every positive integer $n$.

$n = 1, 2, 3$ give $8$, $80$ and $728$. Their highest common factor is $8$.

Conjecture: $8$ divides $3^{2n} - 1$ for all $n \ge 1$. Prove it by induction as in Example 1.

Variations

If a statement is only claimed for $n \ge 4$, say, the base case is $n = 4$.
To prove a statement for odd $n$ only, the base case is $n = 1$ and the step goes from $n = k$ to $n = k + 2$.

Example 4: odd n●●●

Prove that $x^n + 1$ is divisible by $x + 1$ for all odd positive integers $n$.

$n = 1$: $x + 1$ is divisible by $x + 1$.

Assume $x^k + 1 = (x + 1)P(x)$ for odd $k$, where $P(x)$ is a polynomial.

Then $x^{k+2} + 1 = x^2(x^k + 1) - x^2 + 1 = x^2(x + 1)P(x) - (x - 1)(x + 1)$.

This is $(x + 1)\big(x^2 P(x) - x + 1\big)$, so it is divisible by $x + 1$. By induction, the result holds for all odd $n$.

Flashcards

$d$ divides $N$

$N = dM$ for some integer $M$.

Inductive step for divisibility

Write $a^k$ from the assumption, substitute into the $(k + 1)$ expression, then factor out $d$.

Statements for odd $n$ only

Base case $n = 1$, then step from $k$ to $k + 2$.

Practice

Find the largest integer that divides $7^n - 1$ for every positive integer $n$.
Find the largest integer that divides $3^{2n} - 1$ for every positive integer $n$.
Evaluate $5^n + 2 \times 11^n$ when $n = 1$.
In a divisibility proof, assume $5^k - 1 = 4M$. Then $5^{k+1} - 1 = 4(5M + c)$. Find $c$.
In Example 1, the assumption is written as:
To prove a result for all $n \ge 5$, the base case is:
To prove a result for even $n \ge 2$, the inductive step goes from $n = k$ to:
Why is $7(6M + 1) - 1 = 6(7M + 1)$ divisible by $6$?