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?
$\endgroup$ 25 Answers
$\begingroup$$9^{k+1} - 8(k+1) - 1 = 9(9^k - 8k - 1) + (64k + 8)$
See what to do now?
$\endgroup$ 2 $\begingroup$$9^{k+1}-8(k+1)-1=8\cdot9^k+9^k-8k-8-1=8(9^k-1)+9^k-8k-1$
$\endgroup$ $\begingroup$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$.
$\endgroup$ $\begingroup$By the binomial theorem, $9^{n}=(8+1)^{n}=8^2a+\binom{n}{1}8+1=64a+8n+1$, hence the result.
$\endgroup$ 3 $\begingroup$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.
$\endgroup$
