Proof by Induction: Divisibility

A claim about every n

The claim is that $3^{2n}+11$3²ⁿ + 11 is a multiple of 4 for every positive whole number n. Try the first few cases. When n = 1 it is $3^2+11=9+11=20=4\times 5$3² + 11 = 9 + 11 = 20 = 4 × 5. When n = 2 it is $3^4+11=81+11=92=4\times 23$3⁴ + 11 = 81 + 11 = 92 = 4 × 23. When n = 3 it is $3^6+11=729+11=740=4\times 185$3⁶ + 11 = 729 + 11 = 740 = 4 × 185.

Every case checked so far works, but there are infinitely many cases, so checking them one at a time never finishes. Proof by induction proves them all with two steps, as in Proof by Induction: Summing 1 to n. The first step is the base case: show the claim is true for n = 1. That is done already, because 20 = 4 × 5.

Assume one case

The second step is the inductive step. Assume the claim is true for some whole number n = k. That means $3^{2k}+11$3²ᵏ + 11 is a multiple of 4, so $3^{2k}+11=4m$3²ᵏ + 11 = 4m for some whole number m. This assumption is called the induction hypothesis.

The job is to show that the claim must then be true for the next case, n = k + 1. When n = k + 1, the power is 2(k + 1) = 2k + 2, so the next case is $3^{2k+2}+11$3²ᵏ⁺² + 11. We want to show that $3^{2k+2}+11$3²ᵏ⁺² + 11 is a multiple of 4. We may not assume it: it has to follow from the case for k.

The jump from one case to the next

Subtract the case for k from the case for k + 1, to see how much the expression grows in one step: $\left(3^{2k+2}+11\right)-\left(3^{2k}+11\right)$(3²ᵏ⁺² + 11) − (3²ᵏ + 11). The two 11s cancel, which leaves $3^{2k+2}-3^{2k}$3²ᵏ⁺² − 3²ᵏ.

By the index laws, $3^{2k+2}=3^2\times 3^{2k}=9\times 3^{2k}$3²ᵏ⁺² = 3² × 3²ᵏ = 9 × 3²ᵏ. So the difference is $9\times 3^{2k}-3^{2k}$9 × 3²ᵏ − 3²ᵏ: nine lots of $3^{2k}$3²ᵏ take away one lot of $3^{2k}$3²ᵏ, which leaves $8\times 3^{2k}$8 × 3²ᵏ. Since 8 = 4 × 2, every jump from one case to the next is a multiple of 4.

Check it with the cases worked out above. From n = 1 to n = 2 the jump should be $8\times 3^2=8\times 9=72$8 × 3² = 8 × 9 = 72, and 92 − 20 = 72.

Each block is 4. The case n = 2, which is 92, is the case n = 1, which is 20, plus a jump of 72. The 20 is 5 blocks and the jump is 18 more blocks, so 92 is a whole number of blocks too.

The next case is a multiple of 4

The next case is the case before it plus the jump: $3^{2k+2}+11=\left(3^{2k}+11\right)+8\times 3^{2k}$3²ᵏ⁺² + 11 = (3²ᵏ + 11) + 8 × 3²ᵏ. By the induction hypothesis, $3^{2k}+11=4m$3²ᵏ + 11 = 4m, so $3^{2k+2}+11=4m+8\times 3^{2k}$3²ᵏ⁺² + 11 = 4m + 8 × 3²ᵏ.

Both parts carry a factor of 4, so take it outside a bracket: $4m+8\times 3^{2k}=4\left(m+2\times 3^{2k}\right)$4m + 8 × 3²ᵏ = 4(m + 2 × 3²ᵏ). The number in the bracket, $m+2\times 3^{2k}$m + 2 × 3²ᵏ, is a whole number, so $3^{2k+2}+11$3²ᵏ⁺² + 11 is 4 times a whole number, which is a multiple of 4. If the claim is true for n = k, it is true for n = k + 1.

Notice where the factor of 4 comes from. $3^{2k}$3²ᵏ is a power of 3, which is always odd, so it is not a multiple of 4. It is the 8 in front of it that makes the jump a multiple of 4.

The two steps reach every n

The base case shows the claim is true for n = 1. The inductive step with k = 1 then shows it is true for n = 2. The inductive step with k = 2 shows it is true for n = 3, and so on. No whole number is ever skipped, so the claim is true for every positive whole number n.

This is the same chain as in the proof for a sum. The difference is in the inductive step. For a sum, you add the next term to both sides. For divisibility, you compare two cases next to each other and show that the jump between them is a multiple of the divisor.

The base case is n = 1, where the first hop starts. Each hop is the inductive step, which carries the claim from one whole number to the next, so it reaches every n.

The usual mistakes

Assuming the case for k + 1. The inductive step starts from the case for k and must arrive at the case for k + 1. Assuming what you want to prove proves nothing.

Leaving out the base case. The inductive step on its own only says that each case follows from the one before. Without a first true case, there is nothing for it to carry along.

Seven days in a week

The next problem proves that $8^n-1$8ⁿ − 1 is a multiple of 7 in the same way. The jump from one case to the next is $8^{k+1}-8^k=8\times 8^k-8^k=7\times 8^k$8ᵏ⁺¹ − 8ᵏ = 8 × 8ᵏ − 8ᵏ = 7 × 8ᵏ, a multiple of 7. The solution writes the same step as $8^{k+1}-1=8\left(8^k-1\right)+7$8ᵏ⁺¹ − 1 = 8(8ᵏ − 1) + 7, and then uses the result to count whole weeks.