How do you prove $10^n + 3(4)^{n+2} + 5$ is divisible by 9? I was able to do it making the $10^n$ substitution ($10^{k+1} = 10^k (10)$). However, I cant prove it making the $3(4)^{k+2}$ substitution. It should definitely be possible, but I am stuck at $10^{k+1} + 4(9J) - 4(10^k) - 15$ (where J is an integer). I can continue on this path to factories out a $3$, but this is not a $9$. Any help?
Just reduce modulo $9$ :
$$10^n + 3(4)^{n+2} + 5 \equiv 1^n + 3\times 16 \times 4^n + 5 \equiv 1+(3\times-2)\times4^n + 5 \equiv 6(1-4^n)$$
And $4^n = 1$ modulo $3$, so $1-4^n$ is dividible by $3$, so $6(1-4^n)$ is dividible by $9$.
Because $$10^n+3\cdot4^{n+2}+5=10^n-1+3\left(4^{n+2}-1\right)+9.$$
We see that $10^n-1$ is divisible by $9$ and $4^{n+2}-1$ is divisible by $3$.
The inductive step:
By the assumption of the induction we obtain:
$$10^{n+1}+3\cdot4^{n+3}+5=10\left(10^n+3\cdot4^{n+2}+5\right)-18\cdot4^{n+2}-45$$ is divisible by $9$.