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?
 A: One way that is bound to succeed is to notice that this expression depends only on $n\bmod \varphi(9)$, which is $6$. This is because if $n\equiv m \bmod \varphi(9)$ then $10^n \equiv 10^m$ and $4^{n+2} \equiv 4^{m+2}$. This is a consequence of euler's theorem, so this would allow us to only need to check $6$ values.
A: 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!
A: You have shown that $10^n + 3 \cdot 4^{n+2} + 5=3(2+2^{n+4})$ modulo $9$, so it should be enough to show that $2+2^{n+4}=3k$ for some $k$. You can do this by induction.
The base case is obvious, so we will assume $2+2^{2n+4}=3k$ for some n, then:
$$
2+2^{2(n+1)+4}
=
2+4\cdot 2^{2n+4}
=
(2+4(2^{2n+4}+2-2))=
12k-6
=
3(4k-2)
$$
And so, by induction $2+2^{2n+4}=3k$ always holds.
A: 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}$$
A: $$10^n\equiv 1^n\equiv 1\pmod 9$$
$$(3m+1)^t\equiv 1\pmod 3\implies 3(3m+1)^t\equiv 3\pmod 9$$ which then lowers everything to: $$1+3+5\equiv 0\pmod 9$$
A: Here is another way if you know the binomial theorem.
Observe that $$10^n = (1+9)^n = 1 + {n \choose1}9 + \ldots + 9^n = 1 + 9A$$ where $A= {n \choose1}+ \ldots + 9^{n-1}$ and similarly $$4^{n+2} = (1+3)^{n+2} = 1 + (n+2) 3 + {{n+2} \choose 2}3^2 + \ldots + 3^{n+2} = 1 + 3(n+2) + 3^2B$$
So $$10^n + 3 \cdot 4^{n+2} + 5 = 1 + 9A + 3( 1 + 3(n+2) + 3^2B ) + 5 = \color{red}{9} {\left(1 + A + (n+2) + 3B \right) }$$
