For $n \in \mathbb{N}$, show that $4^n + 10 \times 9^{2n-2}$ is divisible by 7 For $n \in \mathbb{N}$, show that $4^n + 10 \times 9^{2n-2}$ is divisible by 7.
I'm not sure how to do this proof so any help would be appreciated.
 A: Induction can certainly be used, but a more direct method will also work as follows - (The trick here is to get to 7 as far as possible, so 9 = 7+2, etc)
$4^n + 10 \times 9^{2n-2}$
= $4^n + 3 \times (7 + 2)^{2n-2}$  (mod 7)
= $4^n + 3 \times 2^{2n-2}$ (mod 7)
= $4^n + 3 \times 4^{n-1}$ (mod 7)
= $4^{n-1}(4 + 3)$ (mod 7)
= $4^{n-1}(0)$ (mod 7)
= $0$ (mod 7)
Edit:-  In fact, because the expression is even, $14$ divides it for all $n$
A: $\begin{align}{\rm mod}\,\ 7\!:\quad\ \ & 4^{\large N} + \color{#c00}{10}\, (\color{#0a0}{9^{\Large 2}})^{\large N-1}\\
\equiv\ & 4^{\large N}\, -\: \color{#c00}4\:(\,\color{#0a0}4\,)^{\large N-1}\\ \equiv\ & 0\end{align}\ \ $ 
by 
$\ \ \ \begin{align} &\color{#c00}{10\equiv -4}\\ &\color{#0a0}{9^{\large 2}\equiv 4}\\ \phantom{.}\end{align}$
A: We have
$$9^{2n-2} = (7+2)^{2n-2} = \sum_{k=0}^{2n-2} \dbinom{2n-2}k 7^k2^{2n-2-k} = 2^{2n-2} + 7M$$
Hence, we have
\begin{align}
4^n+10 \cdot 9^{2n-2} & = 4^n + 10 \cdot (2^{2n-2}+7M) = 4^n+10\cdot 4^{n-1} + 70M = 4^{n-1}(4+10)+70M\\
& = 14(5M+4^{n-1})
\end{align}
Hence, in fact we have that $14$ divides $4^n+10 \cdot 9^{2n-2}$ for all $n \in \mathbb{Z}^+$
A: $9\equiv2\pmod7\implies9^{2m}\equiv2^{2m}\equiv4^m$
$$4^{m+1}+10\cdot9^{2m}\equiv4^{m+1}+10\cdot4^m\equiv4^m(4+10)\equiv0\pmod{14}$$
A: If $n=1$, then 
$$
4^{n} + 10\cdot 9^{2n-2} = 4+10 = 14,
$$
divisible by $7$;
if $n \geq 1$ is an integer such that $4^{n} + 10\cdot 9^{2n-2} = 7k$ for some integer $k \geq 1$, then 
$$
4^{n+1} + 10\cdot 9^{2(n+1) - 2} = 4\cdot 4^{n} + 10\cdot 9^{2n} = 4(4^{n} + 10\cdot 9^{2n-2}) = 28k,
$$
divisible by $7$.
A: $\underline{\text{Proof by induction:}}$
First, show that this is true for $n=1$:
$4^1+10\cdot9^{2-2}=14$
Second, assume that this is true for $n$:
$4^n+10\cdot9^{2n-2}=7k$
Third, prove that this is true for $n+1$:
$4^{n+1}+10\cdot9^{2(n+1)-2}=$
$4^{n+1}+10\cdot9^{2n+2-2}=$
$4^{n+1}+10\cdot9^2\cdot9^{2n-2}=$
$4\cdot4^n+810\cdot9^{2n-2}=$
$4\cdot(\color\red{4^n+10\cdot9^{2n-2}})+770\cdot9^{2n-2}=$
$4\cdot\color\red{7k}+770\cdot9^{2n-2}=$
$28k+770\cdot9^{2n-2}=$
$7\cdot(4k+110\cdot9^{2n-2})$
Please note that the assumption is used only in the part marked red.
A: $4^n+10\cdot 9^{2n-2}=4\cdot 4^{n-1}+(7+3)(9^2)^{n-1}=4\cdot 4^{n-1}+(7+3)(81)^{n-1}$
$=4\cdot 4^{n-1}+7(81)^{n-1}+3(81)^{n-1}=4\cdot 4^{n-1}+7(81)^{n-1}+3(81^{n-1}-4^{n-1}+4^{n-1})$
$=4\cdot 4^{n-1}+7(81)^{n-1}+3(81^{n-1}-4^{n-1})+3\cdot 4^{n-1}=7\cdot 4^{n-1}+7(81)^{n-1}+3(81^{n-1}-4^{n-1})$
$=7\cdot 4^{n-1}+7(81)^{n-1}+3((77+4)^{n-1}-4^{n-1})$
$=7\cdot 4^{n-1}+7(81)^{n-1}+3(\sum_{k=0}^{n-1}{{n-1}\choose k}77^k4^{n-1-k}-4^{n-1})$
$=7\cdot 4^{n-1}+7(81)^{n-1}+3(4^{n-1}+\sum_{k=1}^{n-1}{{n-1}\choose k}77^k4^{n-1-k}-4^{n-1})$
$=7\cdot 4^{n-1}+7(81)^{n-1}+3(\sum_{k=1}^{n-1}{{n-1}\choose k}77^k4^{n-1-k})$
