1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A problem on Induction

  1. Oct 14, 2011 #1
    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. jcsd
  3. Oct 14, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  4. Oct 14, 2011 #3
    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)
     
  5. Oct 14, 2011 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  6. Oct 14, 2011 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Your way of writing it is ok too. Now just put in S(n).
     
  7. Oct 14, 2011 #6
    alright i'll try that and see what i get.
     
  8. Oct 14, 2011 #7
    After trying S(n+1)-S(n) i got the following:

    2*3^n+5^(n+1)-2*3^(n-1)-5^n
     
  9. Oct 14, 2011 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    First correct a couple of errors before you simplify. Where did the '-2' in front come from? Can you find the other error?
     
  10. Oct 14, 2011 #9
    Sorry i typed it in wrong then i fixed it i got
    2*3^n+5^(n+1)-2*3^(n-1)-5^n
     
  11. Oct 14, 2011 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. Oct 14, 2011 #11
    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'
     
  13. Oct 14, 2011 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Why would that be a problem? Just pull out the common factors of 2 and 3^(n-1)...
     
  14. Oct 14, 2011 #13
    what i got was 2(3^n)-2(3^(n-1))+5^n(5-1)
     
  15. Oct 14, 2011 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  16. Oct 14, 2011 #15
    ok i got 2(3^n-3^(n-1))+5^n(5-1)
     
  17. Oct 14, 2011 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    3^n=3*3^(n-1). There's still a common factor of 3^(n-1) you can pull out of the first term.
     
  18. Oct 14, 2011 #17
    can i write it as 2(3(3^(n-1)-3^(n-1)+5^n(4)
     
  19. Oct 14, 2011 #18

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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
  20. Oct 14, 2011 #19
    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
     
  21. Oct 14, 2011 #20
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A problem on Induction
  1. Induction Problem (Replies: 7)

  2. Induction Problem (Replies: 8)

  3. Induction Problem (Replies: 3)

Loading...