# Homework Help: Difficult induction proof

1. Oct 13, 2011

### 1MileCrash

1. The problem statement, all variables and given/known data

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

Prove by induction.

2. Relevant equations

3. 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?

2. Oct 13, 2011

### 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):=22k+1+32k+1

And try using the fact of P(k) that 22k-1+32k-1=5L , to

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

3. Oct 13, 2011

### 1MileCrash

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

4. Oct 13, 2011

### 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.

5. Oct 13, 2011

### 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.

Last edited by a moderator: Oct 13, 2011
6. Oct 13, 2011

### SammyS

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

Last edited: Oct 13, 2011
7. Oct 13, 2011

### 1MileCrash

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

8. Oct 13, 2011

### HallsofIvy

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

Saying anything more would be giving away the answer.

9. Oct 13, 2011

### 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?

10. Oct 13, 2011

### 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).