1. Not finding help here? Sign up for a free 30min 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!

Mathematical induction

  1. Feb 14, 2013 #1
    Hi all, ive been struggling with a large peice of coursework. been quite stressed latley and now im struggling while aproaching my deadline. i need help answering this question.

    Use mathematical induction to show that
    S(n) = 3 × 2 n-1 -2
    is the solution for the recurrence relation:
    T(n) = 2T(n – 1) + 2 for n > 1 and T(1) = 1


    Ive answered so far
    Base T(1)=1
    LS : T2 = 12 = 1 RS: 1T = 1(1) = 1
    So n > 1 is True
    Induction T(n) = 2T(n-1) + 2 for all n > 1

    T(n) = 2T(n – 1) + 3
    = 2T (n -1) + 3
    = 2(2T(n − 2) + 1) + 1
    =2( n + 4) 2n-1 -2
    = 6n -3
    S(n) = 3 × 2 n-1 -2


    Im really confused - can you guys help out
     
    Last edited by a moderator: Feb 14, 2013
  2. jcsd
  3. Feb 14, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Re: Induction

    I am confused by your notation.
    Taken literally, 3 × 2 n-1 -2 = 6n-1-2=6n-3
    But why did you write it so complicated? In addition, it does not satisfy the recurrence relation.
    This is wrong.
    Do you mean n=1?
    What happens here?
     
  4. Feb 14, 2013 #3

    Mark44

    Staff: Mentor

    Re: Induction

    Might this be what the OP means?

    S(n) = 3 * 2 n-1 -2

    As just plain text, this would be written as S(n) = 3 * 2^(n-1) -2
     
  5. Feb 14, 2013 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    How is Sn related to Tn ?

    As Mark44 pointed out, it appears that the formula for Sn should be
    Sn = 3∙2(n-1)-2
    Using the recurrence relation for Tn the first few values in the sequence [Tn] are
    1, 4, 10, 22, 46, …​
     
  6. Feb 15, 2013 #5
    sorry its T2=1 / 2 = 1

    the confusing part is why Sn is related to Tn , im just going to base it on Tn.
    The statment n > 1 is true

    and by the replys i seem to have gone very wrong somewhere?
     
  7. Feb 15, 2013 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I Have no idea what this means! According to "T(n) = 2T(n – 1) + 2 for n > 1 and T(1) = 1", T(2)= 2T(1)+ 2= 2(1)+ 2= 4.

    You still haven't told us what "S(n) = 3 × 2 n-1 -2" means! Is it, as has been suggested, S(n)= 3(2^(n-1))- 2?
     
  8. Feb 15, 2013 #7

    Mark44

    Staff: Mentor

    What you're saying is that 1/2 = 1. Even my dog knows this is not true. If I put only half the usual amount of food in his bowl, he lets me know that I have made a mistake.
     
  9. Feb 16, 2013 #8
    cheers for your help, @ mark, the layout that the coursework has been set is confusing me. im emailing my leacturer to enquire about the questiion.
     
  10. Feb 16, 2013 #9

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Well, I had a typo in Post #4. Quoted above.

    Sn should be:   Sn = 3∙2(n-1) - 2 .

    It appears that your problem should read something like:
    Use mathematical induction to show that the sequence defined by:
    S(n) = 3∙2 n-1 - 2 ​
    is the same sequence defined by recursion as:
    T(n) = 2T(n – 1) + 2 for n > 1 and T(1) = 1​

    (If you calculate the first few terms, you will see that they definitely start out the same.)
     
  11. Feb 16, 2013 #10
    Base S(1)=1, so T(1)=S(1)
    for some n, T(n)=S(n), then:
    T(n+1) = 2T(n)+2 = 2(3×2^(n-1) -2) +2 = 3 × 2^n-4+2 = 3×2^n-2 = S(n+1)

    Proof that T(n)=S(n) then T(n+1)=S(n+1), and as we have T(1)=S(1) i have proven by induction that T(n)=S(n) for any n in the positive integers
     
    Last edited: Feb 16, 2013
  12. Feb 16, 2013 #11

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That is correct.
     
  13. Feb 16, 2013 #12

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    So, you went from deciding to "take a hit" on this problem, to solving it.

    Way to go !
     
  14. Feb 17, 2013 #13
    Thanks all.

    Ive to change T(1) = 1 to T(1)=0 and re write the equation.
     
  15. Feb 18, 2013 #14

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Write down the first several terms of this new sequence.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Mathematical induction
  1. Mathematical induction (Replies: 10)

  2. Mathematical Induction (Replies: 6)

  3. Mathematical induction (Replies: 2)

  4. Mathematical Induction (Replies: 3)

  5. Mathematical induction (Replies: 3)

Loading...