# Induction proof.

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.

• You can for example write $25 = 16 + 9$. Can you see how that lets you use the induction hypothesis? – Daniel Fischer Sep 3 '15 at 18:51
• Maybe first show $2\nmid 5^n$ and $2\nmid 3^n$. – Hagen von Eitzen Sep 3 '15 at 18:53
• @DanielFischer I most certainly can. Thank you for your help. – confusedmathematician34 Sep 3 '15 at 18:55
• @confusedmathematician34 If you do end up with a good answer, feel free to answer your own question (and mark it as best answer). It can help others who search for similar problems in the future and declutters the unanswered questions. Thanks! – nathan.j.mcdougall Sep 3 '15 at 18:57

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

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

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.