How can we use induction to prove that 2^{2n-1} + 3^{2n-1} is divisible by 5?

[1MileCrash]

Homework Statement

2^{2n-1} + 3^{2n-1} is a number divisible by 5.

Prove by induction.

Homework Equations

The Attempt at a Solution

Firstly, solving for n = 1 is true.

I've re-written the statement to be:

2^{2n-1} + 3^{2n-1} = 5L

where L is any natural number.

Now, I assume that it is true for n = k, and then show that if that is so, then it must be true for k + 1.

My problem, is that I don't know what to do to the right side of the equation here to keep a valid statement.

2^{2k-1} + 3^{2k-1} = 5L

2^{2k+1} + 3^{2k+1} = 5L?

What do you do to 5L to keep a valid equation?

 

[Bacle2]

You have to move it, move it! since, as you said, you cannot yet state anything about P(k+1)

Just write the expression as you did:

P(k+1):=2^2k+1+3^2k+1


And try using the fact of P(k) that 2^2k-1+3^2k-1=5L , to

show the expression P(k+1) is also divisible by 5 .

 

[1MileCrash]

So, what are you saying? Repeat induction for the new function?

 

[Bacle2]

No; sorry, I used k instead of n, but it is the same thing. Use your knowledge of the fact that the expression for n is divisible by 5 to show that the expression for n+1 is also divisible by 5; just manipulate and rewrite the expression for n+1 to show it is divisible by 5, using the fact that the expression for n is also divisible by 5.

 

[HallsofIvy]

2^{2(n+1)-1}+ 3^{2(n+1)-1}= 2^{2n+ 1}+ 3^{2n+1}
= 4(2^{2n-1})+ 9(3^{2n-1})

and 9= 5+ 4.

 

[SammyS]

Homework Statement

2^{2n-1} + 3^{2n-1}\text{ is a number divisible by 5.}

Prove by induction.
...

My problem, is that I don't know what to do to the right side of the equation here to keep a valid statement.

2^{2k-1} + 3^{2k-1} = 5L

2^{2k+1} + 3^{2k+1} = 5L?

What do you do to 5L to keep a valid equation?

In Latex, use "\text{ text with s p a c e s. }" to display text.
...

Just pick another integer: 2^{2k+1} + 3^{2k+1} = 5M

 

[1MileCrash]

I don't understand how 9=5+4 in that spot proves anything.

 

[HallsofIvy]

9a+ 4b= (5+4)a+ 4b= 5a+ 4(a+ b)

Saying anything more would be giving away the answer.

 

[1MileCrash]

I think I'm seeing it now.

My end result using your algebra implies 4 times the statement initially assumed to be a multiple of 5, plus 5 times another statement (which is of course a multiple of 5 since it is being multiplied by 5), and a multiple of 5 plus a multiple of 5 is of couse a multiple of 5.

Does it sound like I have a grasp of the proof?

 

[HallsofIvy]

Yes. You have, as I said, 9a+ 4b= (5+4)a+ 4b= 5a+ 4(a+ b). If you have already shown that a+ b is a multiple of 5, that is, a+ b= 5n for some n, then 9a+ 4b= 5a+ 4(5n)= 5(a+4n).