CP 1.1 - Induction for divisibility

You already know

Induction checks a starting case, assumes a statement at one arbitrary integer $k$ and proves the case $k+1$. From A-level Mathematics, factorisation rewrites an expression without changing it; for example, $9x+18=9(x+2)$.

Divisibility

For integers $a$ and $d$, with $d\ne0$, $a$ is divisible by $d$ if $a=dm$ for some integer $m$. For example, $0=7\times0$ and $-21=7\times(-3)$ are divisible by $7$. The number $22$ is not divisible by $7$.

Integer combinations preserve divisibility

If $a=dm$ and $b=dq$, where $d,m,q$ are integers and $d\ne0$, then for integers $u,v$:

Thus every integer combination of multiples of $d$ is another multiple of $d$.

Not in the formula booklet: learn it.

Key idea

The index says which case you are considering; the integer quotient says why that case is divisible. Assuming $f(k)=dm$ lets the quotient change as the proof advances.

Advancing an indexed power

For a non-zero real number $a$, integer constants $p,q$ and integer $k$:

Not in the formula booklet: learn it.

Worked example 1: a power minus one

Question. Prove by induction that $3^{2n}-1$ is divisible by $8$ for all positive integers $n$.

Plan. Check $n=1$, assume $3^{2k}-1=8m$ and rewrite the next case using nine times the whole assumed expression.

At $n=1$,

so the result is true for $n=1$.

Assume $3^{2k}-1=8m$ for an integer $m$, where $k$ is an arbitrary positive integer. Then

Why this step? Nine times $3^{2k}-1$ has a constant term of $-9$. Adding $8$ restores the required constant $-1$.

Answer. Since $9m+1$ is an integer, truth for $n=k$ implies truth for $n=k+1$. The result is true for $n=1$, so it holds for all positive integers $n$, by induction.

Check. At $n=2$, $3^4-1=80=8\times10$. The next quotient after $m=1$ is $9(1)+1=10$.

Worked example 2: correcting the constant

Question. Prove by induction that $3^{2n}+7$ is divisible by $8$ for all positive integers $n$.

Plan. Check the first case, assume $3^{2k}+7=8m$ and compare the next expression with nine times that assumption.

At $n=1$,

so the result is true for $n=1$.

Assume $3^{2k}+7=8m$ for some integer $m$, where $k\ge1$ is an arbitrary integer. Then

Why this step? The bracket contributes $63$, but the required constant is $7$. Subtracting $56$, itself a multiple of $8$, fixes the difference.

Answer. The quantity $9m-7$ is an integer, so truth for $n=k$ implies truth for $n=k+1$. Since the result is true for $n=1$, it is true for all positive integers $n$, by induction.

Check. At $n=2$, $3^4+7=88=8\times11$, and the quotient rule gives $9(2)-7=11$.

Watch out

Wrong: $9\times3^{2k}+7=9(3^{2k}+7)$. The right side has constant term $63$, not $7$. Right: $9\times3^{2k}+7=9(3^{2k}+7)-56$. Expand your bracket once to check the correction.

Exam tip

State “If true for $n=k$, then true for $n=k+1$”. Follow it with the base case and the stated domain. The two cases are linked by your argument; listing them as separate true statements loses that logic.

Worked example 3: a difference of powers

Question. Prove by induction that $5^{2n}-2^{4n}$ is divisible by $9$ for all positive integers $n$.

Plan. Check the first case, assume the difference is $9m$ and compare the next case with $16$ times the assumed difference.

At $n=1$,

so the result is true for $n=1$.

Assume $5^{2k}-2^{4k}=9m$ for an integer $m$, where $k$ is an arbitrary positive integer. Then

Why this step? Multiplying the whole difference by $16$ matches the second power exactly. The unmatched part of the first power is a multiple of $25-16=9$.

Answer. Since $16m+5^{2k}$ is an integer, truth for $n=k$ implies truth for $n=k+1$. The result is true for $n=1$, so it holds for every positive integer $n$, by induction.

Check. At $n=2$, $625-256=369=9\times41$, and $16(1)+25=41$.

Worked example 4: a sum of two powers

Question. Prove by induction that $5^{2n}+8\times2^{4n}$ is divisible by $9$ for all positive integers $n$.

Plan. Verify the new base case, then multiply the whole assumed expression by $16$ and collect the remaining multiple of $9$.

At $n=1$,

so the result is true for $n=1$.

Assume $5^{2k}+8\times2^{4k}=9m$ for an integer $m$, where $k$ is an arbitrary positive integer. Then

Why this step? Keeping the coefficient $8$ inside the bracket lets $16$ account for the entire second term. Only the mismatch in the first power needs correcting.

Answer. Truth for $n=k$ implies truth for $n=k+1$, because $16m+5^{2k}$ is an integer. The result is true for $n=1$, so it is true for all positive integers $n$, by induction.

Check. At $n=2$, $625+8(256)=2673=9\times297$. The quotient rule gives $16(17)+25=297$.

Watch out

Wrong: $5^{2(k+1)}+8\times2^{4(k+1)}=25(5^{2k}+8\times2^{4k})$. The two powers advance by different factors. Right: use one multiplier for the whole expression and include the mismatch explicitly, as in Worked example 4.