Mathematical Induction question: Prove divisibility by $4$ of $5^n + 9^n + 2$

Question

Use mathematical induction to prove that $5^n + 9^n + 2$ is divisible by $4$, where $n$ is a positive integer.

Answer 1

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)$$

Answer 2

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.$$

Answer 3

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.