Using Method of Substitution solve the following recurrence

Using Method of Substitution, solve the following recurrence relation T(N) = 2T(N-1) + 1 With T(l) = 0 [Some of the popular finite series are: 1 + 2 + 3 + ..+ N = N(N+l)/2 1 + r + r^2 + r^3 + ... + r^N = (r^N + 1 - 1)/(r-1) (r is any positive number) 1 + 3 + 5 + ...+(N-2) + N =

Solution

The given series is in arthematic progression,

with first term a = 1

Common difference d = 2

Therefore sum of N terms = a+(N-1)d

= 1+(N-1)2

=. 1+2N-2

= 2N-1

Therefore,. 1+3+5+.....(N-2)+N =. 2N-1