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