# Homework Help: A problem on Induction

1. Oct 14, 2011

### mtayab1994

1. The problem statement, all variables and given/known data
Prove that 8 divides: 1+2x3^(n-1)+5^n for every natural number : n>0

Please I'm having difficulties solving this problem, i just want to understand the concept of how to solve it thank you.

I know that 8 divides: 1+2x3^(n-1)+5^n can also be written as 1+2x3^(n-1)+5^n=8k : with k being a natural number.

Last edited: Oct 14, 2011
2. Oct 14, 2011

### Dick

You want to show it by induction. Let S(n)=1+2*3^(n-1)+5^n. Is S(1) divisible by 8? Now look at S(n+1)-S(n). Can you show that's divisible by 8?

3. Oct 14, 2011

### mtayab1994

I already checked for when n=1 and for that the induction is true because 8/8=1.

By the way is it written as the following?: S(n+1)-S(n)=1+2*3^(n-1)(3)+5^n(5)-S(n)

4. Oct 14, 2011

### Dick

If S(n)=1+2*3^(n-1)+5^n then to get S(n+1) just substitute n+1 for n in S(n). Now take the difference S(n+1)-S(n).

5. Oct 14, 2011

### Dick

Your way of writing it is ok too. Now just put in S(n).

6. Oct 14, 2011

### mtayab1994

alright i'll try that and see what i get.

7. Oct 14, 2011

### mtayab1994

After trying S(n+1)-S(n) i got the following:

2*3^n+5^(n+1)-2*3^(n-1)-5^n

8. Oct 14, 2011

### Dick

First correct a couple of errors before you simplify. Where did the '-2' in front come from? Can you find the other error?

9. Oct 14, 2011

### mtayab1994

Sorry i typed it in wrong then i fixed it i got
2*3^n+5^(n+1)-2*3^(n-1)-5^n

10. Oct 14, 2011

### Dick

Ok, now start trying to write that in a factored form. Combine the two powers of 3. Do the same for the two powers of 5.

11. Oct 14, 2011

### mtayab1994

alright i factored out the powers with 5 and i got 5^n(5-1) but i'm having troubles factoring out the one's with 3's because one is multiplied by '2' and the other by '-2'

12. Oct 14, 2011

### Dick

Why would that be a problem? Just pull out the common factors of 2 and 3^(n-1)...

13. Oct 14, 2011

### mtayab1994

what i got was 2(3^n)-2(3^(n-1))+5^n(5-1)

14. Oct 14, 2011

### Dick

Factor the 2(3^n)-2(3^(n-1)) part. I told you what to do in the last post. And there's nothing wrong with writing 4 instead of 5-1.

15. Oct 14, 2011

### mtayab1994

ok i got 2(3^n-3^(n-1))+5^n(5-1)

16. Oct 14, 2011

### Dick

3^n=3*3^(n-1). There's still a common factor of 3^(n-1) you can pull out of the first term.

17. Oct 14, 2011

### mtayab1994

can i write it as 2(3(3^(n-1)-3^(n-1)+5^n(4)

18. Oct 14, 2011

### Dick

Hmm. Write the first part as 2*3^(n-1)*(something). What's the something? That's what I mean by 'factor out the 3^(n-1)'.

Last edited: Oct 14, 2011
19. Oct 14, 2011

### mtayab1994

i'm sorry i'm getting no where because in class my teacher solves these sorts of problems by just multiplying each side or dividing each side of the equation so he can get some sort of K' which makes the induction true. This is one of the examples:

prove that 9 divides 4^n+6n-1

4(4^n+6n-1)=36k
4^(n+1)+24n-4=36k
4^(n+1)+18n+6n-9+5=36k
4^(n+1)+6n+5=36k-18k+9
4^(n+1)+6n+5=9(4k-2k+1)
4^(n+1)+6(n+1)-1=9k' and he got 9k' from 4k-2k+1

20. Oct 14, 2011

### mtayab1994

And on top of that he never even showed us the induction step: n=k is true and we have to prove that n=k+1 is i had to find that all on my own.