<s>[INST] Proving divisibility by $9$ for $10^n + 3 \times 4^{n+2} + 5$. I am trying to prove that for all $n$, $9$ divides $10^n + 3 \times 4^{n+2} + 5$. I first tried induction on $n$, but couldn't get anywhere with the induction step. I then tried to use modular arithmetic. The furthest I could get was:

As $10 \equiv 1 \mod 9$, $10^n \equiv 1^n = 1$ for all $n$, so modulo $9$, we have
\begin{align*}
10^n + 3 \cdot 4^{n+2} + 5 & = 3 \cdot 4^{n+2} + 6 \\
& = 3\left(4^{n+2} + 2\right) \\
& = 3\left(\left(2^2\right)^{n+2} + 2 \right) \\
& = 3\left(2^{2(n+2)} + 2 \right) \\
& = 3\left(2\left(2^{2(n+2) - 1} + 1\right) \right)
\end{align*}

I need to something get a factor of $3$ to show that the entire expression is divisible by $9$ and hence equal to $0$, mod $9$. But, with a sum of even terms, this does not appear possible.
Any hints on how to proceed would be appreciated. Is induction the standard way to prove something like this?
 [/INST] We can construct one of the possible proofs as follows:
$$\begin{align}&10^n + 3 \times 4^{n+2} + 5 \mod 9
\\
\iff &10^n + 3 \times 4^{n+2} -4\mod 9\\
\iff &10^n-1^n+3 \times 4^{n+2} -3\mod 9\\
\iff &3\left(4^{n+2}-1\right)\mod 9\\ \iff
&4^{n+2}-1^{n+2} \mod 3 =0.\end{align}$$
</s>