Results 1 to 2 of 2

Math Help - Apply telescoping to determine explicit formula for T(n)

  1. #1
    Junior Member
    Joined
    Mar 2008
    Posts
    56

    Apply telescoping to determine explicit formula for T(n)

    Hi everyone.
    I need some help with finding the pattern for explicit formula so:

    T(n) = 2T(n-1) + 1 : T(0) = 0

    T(n-1) = 2T(n-2) +1
    T(n-2) = 2T(n-3) +1
    T(n-3) = 2T(n-4) +1
    T(n-4) = 2T(n-5) +1
    `
    `
    `
    T(1) = 2T(0) +1 = 1

    Working:

    T(n-3) = 2T(n-4) +1

    Substituting T(n-4)+1

    T(n-3) = 2[2T(n-5)+1] +1
    T(n-3) = 2[2T(n-5)] +1 + 2
    T(n-3) = 2^2T(n-5) +1 + 2

    So the pattern is

    T(n) = 2^(n-1) + sum from i=0 to n-2 where 2^i

    My question is: I do know how to do telescoping but i do not know how to find the pattern. Can anybody show me step by step how to find it.

    For any help i will be appreciate.

    Cheers
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,980
    Thanks
    1643
    Quote Originally Posted by Snowboarder View Post
    Hi everyone.
    I need some help with finding the pattern for explicit formula so:

    T(n) = 2T(n-1) + 1 : T(0) = 0

    T(n-1) = 2T(n-2) +1
    T(n-2) = 2T(n-3) +1
    T(n-3) = 2T(n-4) +1
    T(n-4) = 2T(n-5) +1
    `
    `
    `
    T(1) = 2T(0) +1 = 1

    Working:

    T(n-3) = 2T(n-4) +1

    Substituting T(n-4)+1

    T(n-3) = 2[2T(n-5)+1] +1
    T(n-3) = 2[2T(n-5)] +1 + 2
    T(n-3) = 2^2T(n-5) +1 + 2

    So the pattern is

    T(n) = 2^(n-1) + sum from i=0 to n-2 where 2^i

    My question is: I do know how to do telescoping but i do not know how to find the pattern. Can anybody show me step by step how to find it.

    For any help i will be appreciate.

    Cheers
    It isn't really "telescoping" but if T(0)= 0, then T(1)= 2T(0)+ 1= 1= 2-1, T(2)= 2T(1)+ 1= 2+ 1= 3= 4-1, T(3)= 2T(2)+ 1= 6+1= 7-1, T(4)= 2(T(3))+ 1= 14+1= 15= 16-1.

    At this point, I would "guess" that T(n)= 2^n-1 and then prove it by induction on n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with Explicit Sequence Formula
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 24th 2010, 07:33 PM
  2. how to apply quadratic formula to this
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 23rd 2009, 12:04 PM
  3. Replies: 0
    Last Post: November 5th 2009, 11:41 AM
  4. explicit formula
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 19th 2008, 12:23 PM
  5. Determine r for Explicit Formula
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 13th 2007, 02:37 PM

Search Tags


/mathhelpforum @mathhelpforum