Mathematical Induction question: Prove divisibility by $4$ of $5^n + 9^n + 2$ Use mathematical induction to prove that $5^n + 9^n + 2$ is divisible by $4$, where $n$ is a positive integer.
 A: With induction: $5^1+9^1+2=16$ is divisible by $4$. If $5^k+9^k+2$ is divisible by $4$ for some $k\ge 1$, then $5^{k+1}+9^{k+1}+2=\left(5^k+9^k+2\right)+4\left(5^k+2\cdot 9^k\right)$ is also divisible by $4$.
Without explicit induction: $$5^n+9^n+2=\left(5^n-1\right)+\left(9^n-1\right)+4$$
$$=(5-1)\left(5^{n-1}+5^{n-2}+\cdots+1\right)+(9-1)\left(9^{n-1}+9^{n-2}+\cdots+1\right)+4$$
$$=4\left(\left(5^{n-1}+5^{n-2}+\cdots+1\right)+2\left(9^{n-1}+9^{n-2}+\cdots+1\right)+1\right)$$
A: First, show that this is true for $n=1$:
$5^1+9^1+2=16$
Second, assume that this is true for $n$:
$5^n+9^n+2=4k$
Third, prove that this is true for $n+1$:
$5^{n+1}+9^{n+1}+2=$
$5\cdot5^{n}+9\cdot9^{n}+2=$
$(1+4)\cdot5^{n}+(1+8)\cdot9^{n}+2=$
$5^{n}+4\cdot5^{n}+9^{n}+8\cdot9^{n}+2=$
$\color\red{5^{n}+9^{n}+2}+4\cdot5^{n}+8\cdot9^{n}=$
$\color\red{4k}+4\cdot5^{n}+8\cdot9^{n}=$
$4(k+5^{n}+2\cdot9^{n})$

Please note that the assumption is used only in the part marked red.
A: Hint Note that
$$ 5^{n+1}+9^{n+1}+2 = 5\cdot 5^{n}+9\cdot 9^n+2 = 9\cdot (5^n+9^n+2)-4\cdot 5^n-16.$$
