Thread: 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

Originally Posted by Snowboarder

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)= and then prove it by induction on n.