Prove using mathematical induction: for $n \ge 1, 5^{2n} - 4^{2n}$ is divisible by $9$

Question

I have to prove the following statement using mathematical induction.

For all integers, $n \ge 1, 5^{2n} - 4^{2n}$ is divisible by 9.

I got the base case which is if $n = 1$ and when you plug it in to the equation above you get 9 and 9 is divisible by 9.

Now the inductive step is where I'm stuck.

I got the inductive hypothesis which is $ 5^{2k} - 4^{2k}$

Now if P(k) is true than P(k+1) must be true. $ 5^{2(k+1)} - 4^{2(k+1)}$

These are the step I gotten so far until I get stuck:

$$ 5^{2k+2} - 4^{2k+2} $$ $$ = 5^{2k}\cdot 5^{2} - 4^{2k} \cdot 4{^2} $$ $$ = 5^{2k}\cdot 25 - 4^{2k} \cdot 16 $$

Now after this I have no idea what to do. Any help is appreciated.

Answer 1

You're very close. Now add and subtract $4^{2k}$ in the first term to obtain $$ 5^{2k}\cdot 25-4^{2k}\cdot 16=25\cdot (5^{2k}-4^{2k})+(25-16)\cdot 4^{2k}=25\cdot (5^{2k}-4^{2k})+9\cdot 4^{2k} $$

The first term is divisible by $9$ by the induction hypothesis, hence the whole expression is divisible by $9$.

Answer 2

The inductive hypothesis is

$$(5^{2n}-4^{2n})\bmod9=0.$$

Then

$$(5^{2n+2}-4^{2n})\bmod9=(25\cdot5^{2n}-16\cdot4^{2n})\bmod9=(9\cdot5^{2n}+16(5^{2n}-4^{2n}))\bmod9=0.$$

Answer 3

The induction hypothesis can be written $$ 5^{2k}-4^{2k}=9m $$ for some integer $m$. Therefore $5^{2k}=4^{2k}+9m$ and so $$ 5^2\cdot5^{2k}-4^2\cdot4^{2k}= 25(9m+4^{2k})-16\cdot4^{2k}= 9\cdot 25m+(25-16)\cdot 4^{2k}= 9\cdot 25m-9\cdot 4^{2k} $$

---

Alternatively, $4\equiv -5\pmod{9}$, so $$ 5^{2k}-4^{2k}\equiv 5^{2k}-(-5)^{2k}\equiv 5^{2k}-5^{2k}\pmod{9} $$

Answer 4

$\begin{align}{\bf Hint}\qquad\qquad\qquad\qquad\,\ \color{#c00}{25} &=\,\ \color{#c00}{16 + 9}\\ 25^{\large N} &=\,\ 16^{\large N}\! +\! 9j\\ \Rightarrow\,\ 25^{\large N+1}\! = \color{#c00}{25}\cdot 25^{\large N} &= (16^{\large N}\!+\!9j)(\color{#c00}{16+\!9}) = 16^{\large N+1} +9\,(\cdots)\ \end{align}$

---

Or, said mod $\,9\!:\,\ \begin{align} 25&\equiv 16\\ 25^{\large N}&\equiv 16^{\large N}\end{align}\ \Rightarrow\, 25^{\large N+1}\equiv 16^{\large N+1}\,$ by the Congruence Product Rule

Or, $ $ equivalently, $\ \big[25\equiv 16\big]^{\large N}\!\Rightarrow\, 25^{\large N}\!\equiv 16^{\large N}\, $ by the Congruence Power Rule, which is an inductive extension of the Product Rule.