Proving $9^n - 8n - 1$ is divisible by $8^2$ for $n\ge 0$? My textbook provided the following proof:


  
*Base case: When $n=0, 9^n-8n-1=0=64\cdot0$, so $64\mid\left(9^n-8n-1\right)$.
Induction step: Suppose that $n\in\mathbb N$ and $64\mid\left(9^n-8n-1\right)$. Then there is some integer $k$ such that $9^n-8n-1=0=64k$. Therefore:
$$\begin{align}
9^{n+1}-8(n+1)-1&=9^{n+1}-8n-9\\
&=9^{n+1}-72n-9+64n\\
&=9\left(9^n-8n-1\right)+64n\\
&=9(64k)+64n\\
&=64(9k+n)
\end{align}$$
so $64\mid\left(9^{n+1}-8(n+1)-1\right)$.

What I don't understand is how the equation goes from 
$$= 9^{n+1} - 8n - 9$$
to 
$$= 9^{n+1} - 72n - 9 + 64n$$
 A: Express $8n$ as $72n-64n$. We hence have
$$9^{n+1} - {\color{red}{8n}} - 9 = 9^{n+1} - \color{red}{(72n-64n)} - 9 = 9^{n+1} \color{red}{- 72n + 64n} - 9 = 9^{n+1} - \color{red}{72n} - 9 + \color{red}{64n}$$
A: The algebra follows by $\, -8n\, =\, -72n + 64n.\,$ The proof is more conceptually viewed as the standard inductive computation  of the first two terms of a Binomial Theorem expansion, i.e.
$\begin{align} (1+ a)^n\, \ \  =&\,\ \ 1 + na + \color{#0a0}k a^2,\,\ \color{#0a0}{k\in\Bbb Z},\qquad\qquad\, {\rm i.e.}\ \ P(n)\\[.2em]
\Rightarrow\ (1+a)^{\color{#c00}{n+1}}\! =&\  (1+na+ka^2)(1\!+\!a)\\[.2em]  
 =&\,\ \ 1+\color{#c00}na+\color{#0a0}ka^2 + \color{#c00}{1}\cdot a+\color{#0a0}na^2\!+\color{#0a0}{ka} a^2\\[.2em]  
 =&\,\ \ 1+(\color{#c00}{n\!+\!1})a + \color{#0a0}{K}a^2,\ \ \color{#0a0}{K\in\Bbb Z},\quad {\rm i.e.}\ \ P(\color{#c00}{n\!+\!1})\end{align}$
or, more simply: $\,\ (1\!+\!na)(1\!+\!a) \equiv 1\!+\!(n\!+\!1)a\, \pmod{\!a^2}\ $ if you know modular arithmetic, where we have used the fundamental Congruence Product Rule.
OP is case $\,a=8,\,$ i.e. $\,9^n\! = (1\!+\!8)^n = 1+8n + 8^2\color{#0a0} {k,\ k\in\Bbb Z,\ \rm so}$ $\ 8^2\mid 9^n-8n-1$
A: Use induction.
You know that the assertion is true for $n = 1.$
Assume that the assertion is true for $n = N.$
Then, the problem reduces to showing that
$$(64) ~\text{divides}~ \{[9^{N+2} - 8(N+1)] - [9^{N+1} - 8N]\}$$
$$ ~=~ [9^{N+1}(9 - 1)] - 8 = 8 \times [9^{N+1} - 1].$$
So, the problem reduces to showing that
$$(8) ~\text{divides}~ [9^{N+1} - 1].$$
However, this is immediate, since it is known that for any positive integer $n$, the polynomial $(x^n - 1)$ is divisible by $(x - 1).$
Alternatively, you could reason that since $9 \equiv 1\pmod{8}$, you must have that $9^{N+1} \equiv 1\pmod{8}.$
