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$$

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}.$
