Proving 8 divides 1+2x3^(n-1)+5^n for all n>0

[mtayab1994]

Homework Statement

Prove that 8 divides: 1+2x3^(n-1)+5^n for every natural number : n>0Please 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.

 

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

 

[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)

 

[Dick]

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)

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

 

[Dick]

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)

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

 

[mtayab1994]

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

 

[mtayab1994]

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

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

 

[Dick]

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

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

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

 

[mtayab1994]

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

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

 

[Dick]

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

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.

 

[mtayab1994]

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.

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'

 

[Dick]

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'

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

 

[mtayab1994]

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

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

 

[Dick]

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

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.

 

[mtayab1994]

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.

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

 

[Dick]

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

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

 

[mtayab1994]

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

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

 

[Dick]

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

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

 

[mtayab1994]

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

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

 

[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

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.

 

[Dick]

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.

Ok, but we are getting off the track here. I'm trying to get you to show that S(n+1)-S(n)=(something)*3^(n-1)+4*5^n and what that (something) is. You got the 4 in front of the 5^n just fine. I'm not sure why are having problems with the 3^(n-1) part. And then go on from there to tell me why S(n+1)-S(n) is divisible by 8. Then try and tell me why that solves your induction problem. That's the program. You seem to be getting bogged down in the algebra part.

 

[mtayab1994]

Ok, but we are getting off the track here. I'm trying to get you to show that S(n+1)-S(n)=(something)*3^(n-1)+4*5^n and what that (something) is. You got the 4 in front of the 5^n just fine. I'm not sure why are having problems with the 3^(n-1) part. And then go on from there to tell me why S(n+1)-S(n) is divisible by 8. Then try and tell me why that solves your induction problem.

alright I'm working on that and by the way is that proof true for 9 divides 4^n+6n-1

 

[mtayab1994]

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

 

[mtayab1994]

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

then i came out with 4(3^(n-1)+5^n)

 

[Dick]

then i came out with 4(3^(n-1)+5^n)

Good! Now you can clearly see that's divisible by 4, right? Can you give me a reason why it must also be divisible by 8?

 

[mtayab1994]

it's also divisible by 8 because 8 is a multiple of 4. So there for S(n-1)-S(n) is divisible by 8.

 

[Dick]

it's also divisible by 8 because 8 is a multiple of 4. So there for S(n-1)-S(n) is divisible by 8.

I don't trust your reasoning there. 3*4 is a multiple of 4. But it's not a multiple of 8. Is 3^(n-1) odd or even? Same question for 5^n.

 

[mtayab1994]

yea i found the answer:
3^(n-1) is odd and so is 5^n and the sum of two odd numbers is an even number so therefore 8 divides any number 4k' for k' is an even number.

 

[Dick]

yea i found the answer:
3^(n-1) is odd and so is 5^n and the sum of two odd numbers is an even number so therefore 8 divides any number 4k' for k' is an even number.

Right. And you see how that makes the induction work, yes?

 

[mtayab1994]

Right. And you see how that makes the induction work, yes?

Yes thank you for your help. I really appreciate it.