# Help proving $9^n-8n-1$ is divisible by $8$ for all $n > 1$ by induction

I have been trying to prove that $9^n-8n-1$ is divisible by $8$ for all $n$ integers greater than 1. My progress: Let $n = 2$. This gives us the expression equal to $64$ which is a factor of 8. Now assume it is true for $n=k$ . for $n = k+1$ :

$$9^{k+1} - 8(k+1) - 1$$ $$= (8+1)^{k} \times (8+1) -8k - 8 -1$$

I keep getting stuck on this part. Can someone please hint me how I can proceed by using INDUCTION only?

$9^{k+1} - 8(k+1) - 1 = 9(9^k - 8k - 1) + (64k + 8)$

See what to do now?

• I'm not sure why you took out $9$ as a common factor and not $8$ – Aspiring Mathlete Oct 31 '14 at 14:53
• We want to show that $9^k - 8k - 1$ being divisible by $8$--the inductive hypothesis--implies $9(9^k - 8k - 1) + (64k + 8)$ is divisible by $8$. Now, the inductive hypothesis implies that $9(9^k - 8k - 1)$ is divisible by $8$ and so therefore is $9(9^k - 8k - 1) + (64k + 8) = 9(9^k - 8k - 1) + 8(8k + 1)$. – Simon S Oct 31 '14 at 15:00

$9^{k+1}-8(k+1)-1=8\cdot9^k+9^k-8k-8-1=8(9^k-1)+9^k-8k-1$

Assume $9^k -8k -1$ is divisible of 8. Then $$9^{k+1}-8(k+1)-1\equiv 1^{k+1}-0(k+1)-1\equiv1-0-1\equiv 0\pmod 8$$ so $9^{k+1}-8(k+1)-1$ is divisible by 8.

What? We didn't use the induction hypothesis? No matter -- the conclusion is no less true for that.

Alternatively, without modular arithmetic: By the binomial theorem $$9^{k+1} = (1+8)^{k+1} = \binom{k+1}0 1^{k+1}8^0 + (\text{terms all involving factors of }8) = 1 + 8c$$ for some $c$. Therefore $$9^{k+1}-8(k+1)-1 = 1 + 8c - 8(k+1) - 1 = 8(c-k-1)$$ which is clearly divisible by $8$.

By the binomial theorem, $9^{n}=(8+1)^{n}=8^2a+\binom{n}{1}8+1=64a+8n+1$, hence the result.

• Induction appears in the binomial theorem... – lhf Oct 31 '14 at 15:04
• Why show the $\binom n18$ term separately? – hmakholm left over Monica Oct 31 '14 at 15:54
• @HenningMakholm, that's what the binomial theorem gives, but perhaps it's too much. – lhf Oct 31 '14 at 16:06

It is enough to prove $9^n - 1$ is a multiple of 8. ($8n$ being a multiple of 8, subtracting this from $9^n-1$, we obtain a multiple of 8). Now, \begin{align*} (9^{n+1}-1) - (9^n-1) = 9^n(9-1) = 8\cdot 9^n \end{align*} and we are through.