<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] Method 1: without using induction
$10^n+3. 4^{n+2}+5=(1+9)^n+3(1+3)^{n+2}+5$
Which after applying binomial expansion, takes the form
$1+3(1+3(n+2))+5+9k$ for some positive integer k. This reduces to $9(n+3)+9k$. Hence, $9$ divides the expression for all $n$.
Method 2: Using induction
Let $P(n)$ denote the statement that $10^n+3.4^{n+2}+5$ be divisible by $9$. Clearly, $P(1)$ is true.
Let $P(n)$ be true.
Then, $P(n+1)= 10^{n+1}+3.4^{n+3}+5= 10^n(9+1)+ 3(3+1).4^{n+2}+5$
which reduces to $10^n+4^{n+2}+5+9.10^n+9.4^{n+2}$ which is nothing but $P(n)$ added to a number divisible by $9$. Hence $P(n+1)$ is also true. The statement $P(n)$ is divisible by $9$ for all $n$.
So yes, induction can be of great use in these problems!
</s>