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.

You can for example write $25 = 16 + 9$. Can you see how that lets you use the induction hypothesis? — Daniel Fischer, Sep 03 '15 at 18:51
@DanielFischer I most certainly can. Thank you for your help. — confusedmathematician34, Sep 03 '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 03 '15 at 18:57

score 4 · Accepted Answer · edited Sep 03 '15 at 19:21

4

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

edited Sep 03 '15 at 19:21

Euler88 ...

2,090

answered Sep 03 '15 at 19:04

confusedmathematician34

51

score 0 · Answer 2 · answered Sep 03 '15 at 19:34

0

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

answered Sep 03 '15 at 19:34

Adi Dani

16,949

score 0 · Answer 3 · answered Sep 03 '15 at 19:40

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.

Induction proof.

3 Answers3