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