<s>[INST] 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.
 [/INST] 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)$$
</s>