Results 1 to 3 of 3

Math Help - Mathematical Induction

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    7

    Mathematical Induction

    Hi there,

    I'm totally dumbfounded by this question. Could anyone give me a basis on where to start so I can at least try to work it out myself?

    Use mathematical induction to show that:

    S(n) = 3*2^{n-1} -2
    is the solution for the reccurence relation:
    T(n)=2T(n-1)+2 for   n > 1 and T(1) = 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2009
    Posts
    91
    To prove T(n)=S(n) for all positive integers n all you have to do is show

    (i) that T(1)=S(1), and
    (ii) that if T(k-1)=S(k-1) for some k>1 then also T(k)=S(k) for that very same k.

    Here we go.

    Let S(n)=3\times2^{n-1}-2.

    Initial step: S(1)=3\times2^0-2=3-2=1, so T(1)=S(1).

    Inductive step: Assume that T(k-1)=S(k-1) for some k>1.

    Then T(k)=2T(k-1)+2=2S(k-1)+2=2(3\times2^{k-2}-2)+2=3\times2^{k-1}-2=S(k).

    Thus, by the principle of induction, T(n)=S(n) for all positive integers n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    7
    Thanks, that helped a lot. I have a follow up question here.

    If 1 is added to the recurrence relation such that:

    T(n) = 2T(n-1) + 3 for n > 1 and T(1) = 0

    What is the new equation for S(n)?
    Prove it by induction.
    Am I basically reversing the steps in the first answer to come up with a new equation for S(n)? This is what I've come up with:

    T(k) = 2T(k-1)+3=2S(k-1)+3=3(3*2^{k-2}-2)+3=3x2^{k-1}-3=S(k)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2010, 04:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2010, 06:54 AM
  3. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 06:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 09:35 AM

Search Tags


/mathhelpforum @mathhelpforum