## 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

��(��) = 2��(�� − 1) + 1
��(�� − 1) = 2��(�� − 2) + 1
��(�� − 2) = 2��(�� − 3) + 1
��(�� − 3) = 2��(�� − 4) + 1
��(�� − 4) = 2��(�� − 5) + 1
.
.
.
�� 1 = 2�� 0 + 1 = 1
Working:
��(�� − 3) = 2��(�� − 4) + 1
������������������������ ��(�� − 4)
��(�� − 3) = 2[2��(�� − 5) + 1] + 1
�� �� − 3 = 2 2�� �� − 5 + 1 + 2
�� �� − 3 = 22�� �� − 5 + 1 + 2
Further working (if you still don’t spot a pattern, do another step):
��(�� − 2) = 2��(�� − 3) + 1
������������������������ ��(�� − 3)
�� �� − 2 = 2[22�� �� − 5 + 1 + 2] + 1
�� �� − 2 = 2[22�� �� − 5 ] + 1 + 2 + 4
�� �� − 2 = 23�� �� − 5 + 1 + 2 + 4

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