1.7 - Proof by induction for divisibility | Cambridge A-Level Further Mathematics

A divisibility proof must show an integer multiple, not just an expression that looks factorisable. In this part of 1.7, you will write precise hypotheses, connect successive exponential expressions, and justify the parity and domain statements that complete a proof.

The induction hypothesis

Why is $5^n-1$ divisible by $4$ however large the positive integer $n$ is? The first values are $4,24,124$ . Writing each as $4$ times an integer suggests what the induction hypothesis should say.

For integers $d\ne0$ and $a$ , saying that $a$ is divisible by $d$ means that $a=dm$ for some integer $m$ . An algebraic factor $d$ is enough only if the remaining factor is an integer on the stated domain.

Divisibility hypothesis

To assume that an integer expression $F(k)$ is divisible by $d$ , write

F(k)=dm\quad\text{for some integer }m.

where $k$ is an arbitrary integer in the allowed range. The integer $m$ may depend on $k$ ; it need not have the same value in the next case.

For example, “assume $5^k-1$ ” is only an expression. “Assume $5^k-1=4m$ for some integer $m$ ” is the statement you can use. The same idea can be written in words, provided the expression and its divisibility are both explicit.

Worked example 1: exposing the assumed multiple

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

Plan. Rewrite the next expression so that $5^k-1$ appears unchanged inside a bracket.

At $n=1$ , $5-1=4$ , which is divisible by $4$ . Assume, for an arbitrary positive integer $k$ , that

5^k-1=4m\qquad(m\in\mathbb Z).

Then

\begin{aligned} 5^{k+1}-1 &=5(5^k-1)+4 &&\text{reveal the old expression}\\ &=5(4m)+4 &&\text{hypothesis}\\ &=4(5m+1). \end{aligned}

Because $m$ is an integer, $5m+1$ is an integer, establishing divisibility in the next case.

Answer. The base case and the implication from $k$ to $k+1$ prove that $5^n-1$ is divisible by $4$ for every positive integer $n$ , by induction.

Check. At $n=4$ , direct calculation gives $625-1=624=4\times156$ , a new numerical check.

Change the exponential base from $5$ to $9$ . The same construction now reveals a multiple of $8$ , the amount by which the base exceeds $1$ .

Worked example 2: a different divisor

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

Plan. Use $9^{k+1}-1=9(9^k-1)+8$ .

At $n=1$ , the expression is $8$ . Assume $9^k-1=8m$ , where $m$ is an integer and $k$ is an arbitrary positive integer. Then

\begin{aligned} 9^{k+1}-1 &=9(9^k-1)+8\\ &=9(8m)+8\\ &=8(9m+1). \end{aligned}

The factor $9m+1$ is an integer, so the next expression is divisible by $8$ .

Answer. Hence $9^n-1$ is divisible by $8$ for every positive integer $n$ , by induction.

Check. At $n=3$ , $9^3-1=728=8\times91$ . The quotient is an integer, as the proof predicts.

You do not need to calculate the quotient in advance. Naming an integer quotient makes the assumption usable and shows why the new quotient is also integral.

Watch out

$F(k)=dm$ with $m$ merely real says nothing about divisibility: every real number can be written that way. State that $m$ is an integer.

Make that integer condition explicit in your own proof.

Reusing the previous case

When two exponentials appear, comparing successive expressions can be simpler than trying to factor the next expression immediately.

Let $F(n)=4^n+10^n-2$ . The difference

\begin{aligned} F(k+1)-F(k) &=(4^{k+1}-4^k)+(10^{k+1}-10^k)\\ &=3\cdot4^k+9\cdot10^k \end{aligned}

removes the constant and produces useful factors. If $F(k)$ and this difference are multiples of $d$ , then their sum $F(k+1)$ is a multiple of $d$ .

Problem-solving

Try $F(k+1)-F(k)$ , or $F(k+1)-aF(k)$ when a multiplier $a$ creates cancellation. After proving the difference is divisible, explicitly reconnect it to $F(k+1)$ .

First prove a multiple of $3$ . Then keep the same expression but strengthen the requested divisor to $6$ ; that extra factor of $2$ must be explained.

Worked example 3: a difference with an immediate factor

Question. Prove by induction that $F(n)=4^n+10^n-2$ is divisible by $3$ for every positive integer $n$ .

Plan. Show that $F(k+1)-F(k)$ is a multiple of $3$ , then add the assumed multiple.

At $n=1$ , $F(1)=4+10-2=12$ , a multiple of $3$ . Assume $F(k)=3m$ for an integer $m$ , where $k$ is an arbitrary positive integer. Then

\begin{aligned} F(k+1)-F(k) &=3\cdot4^k+9\cdot10^k\\ &=3(4^k+3\cdot10^k). \end{aligned}

The bracket is an integer. Reconnecting to the expression we need,

F(k+1)=3m+3(4^k+3\cdot10^k) =3(m+4^k+3\cdot10^k).

Thus $F(k+1)$ is a multiple of $3$ .

Answer. $4^n+10^n-2$ is divisible by $3$ for every positive integer $n$ , by induction.

Check. At $n=2$ , direct calculation gives $16+100-2=114=3\times38$ .

A multiple of $3$ need not be a multiple of $6$ . For the stronger result, use the fact that both powers in the difference are even when $k\geq1$ .

Worked example 4: supplying the missing parity factor

Question. Prove by induction that the same $F(n)=4^n+10^n-2$ is divisible by $6$ for every positive integer $n$ .

Plan. Keep the difference calculation, but show its bracket is even as well as integral.

At $n=1$ , $F(1)=12=6\times2$ . Assume $F(k)=6m$ for an integer $m$ and an arbitrary positive integer $k$ . As before,

F(k+1)-F(k)=3(4^k+3\cdot10^k).

Since $k\geq1$ , both $4^k$ and $10^k$ are even. More explicitly,

\begin{aligned} 4^k+3\cdot10^k &=2\bigl(2^{2k-1}+15\cdot10^{k-1}\bigr)\\ &=2q. \end{aligned}

where $q$ is an integer because both exponents are nonnegative. Therefore

F(k+1)=F(k)+6q=6m+6q=6(m+q).

This establishes the required next case.

Answer. The expression is divisible by $6$ for every positive integer $n$ , by induction.

Check. At $n=3$ , direct calculation gives $64+1000-2=1062=6\times177$ , confirming the stronger divisor in a new case.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Mechanics

Further Probability and Statistics

1.7 - Proof by induction for divisibility

The induction hypothesis

Reusing the previous case

Continue this lesson.

Learn faster with Nova