Induction proof.

Question

Homework question, so just a pointer would be nice, for starters.

I'm trying to prove $2 \mid 5^{2n} - 3^{2n}$ by induction.

I use $n=0$ as the base step, and assume $5^{2n} - 3^{2n} = 2k$ as my inductive hypothesis. Then for the inductive step I do $$5^{2n+2} - 3^{2n+2} = 25*5^{2n}-9*3^{2n}$$ and then I have no clue what to do, as I see no way to make the expression nicer.

Answer 1

As explained by Daniel in the comments, writing 25 as 16 + 9 allows us to use the inductive hypothesis. $$5^{2n+2}−3^{2n+2}=$$ $$=25\cdot 5^{2n}−9\cdot 3^{2n}=$$ $$=(16 + 9)\cdot 5^{2n}−9\cdot 3^{2n}=$$ $$=16\cdot 5^{2n}+9(5^{2n}-3^{2n})=$$ $$=16\cdot 5^{2n}+9\cdot 2k=$$ $$=2\cdot (8\cdot 5^{2n}+9k)$$ $$\Box$$

Answer 2

HINT: $$5^{2(n+1)} - 3^{2(n+1)}=5^{2n+2}-3^{2n+2}=25\cdot5^{2n}-9\cdot3^{2n}=$$ $$=25\cdot5^{2n}-25\cdot3^{2n}+16\cdot3^{2n}=25(5^{2n} - 3^{2n})+2\cdot8\cdot3^{2n}$$

Answer 3

Here is an alternative, simpler way:

• Prove that if $x$ and $y$ are odd then $x-y$ is even.

• Prove that if $x$ and $y$ are odd then $xy$ is odd.

• Prove that if $x$ is odd then $x^n$ is odd. Use induction here.

Now note that both $5$ and $3$ are odd.