# How to derive a closed form of a simple recursion?

Consider: $$T(n) = 2 T(n-1) + 1$$ with $T(1)$ a positive integer constant $a$.

I just stuck in finding a closed form for this simple recursion function. I would appreciate it, if someone gives me a hint.

-
Look for a closed form $T(n)=A2^n+B$, with $A,B$ constants. This is not magic: there is a theory of linear recurrent sequences. –  1015 Apr 9 '13 at 14:27
@julien: this is more of an answer than a comment, don't you think? –  Ron Gordon Apr 9 '13 at 14:48
Consider the recurrence $U(n) = T(n) + 1$. –  Sammy Black Apr 9 '13 at 14:48
@RonGordon I seem to be in a commenting mood today... –  1015 Apr 9 '13 at 14:50
@julien: you know, you can take something for that. –  Ron Gordon Apr 9 '13 at 14:52

If you try for $n=2,3,4$ you can see the pattern. When $n=2$ you have that $$T(2)=2T(1)+1=2a+1$$ When $n=3$ then $$T(3)=2T(2)+1=2(2a+1)+1=2^2a+2+1$$ When $n=4$ $$T(4)=2T(3)+1=2(2^2a+2+1)+1=2^3a+2^2+2+1$$ Claim, if $T(n)=2T(n-1)+1$ and $T(1)=a$, then $T(n)=2^{n-1}a+2^{n-2}+2^{n-3}+\ldots+2^2+2^0=2^{n-1}a+2^{n-1}-1$
A proof with generating functions: Let $$f(X) := \sum_{n=1}^{\infty} T(n) X^n$$ be a formal power series (we don't care about convergence); then you have $$f(X) = aX +\sum_{n=2}^{\infty} (2T(n-1) + 1)X^n$$ $$= aX + 2Xf(X) + \sum_{n=2}^{\infty} X^n$$ $$=2Xf(X) + \frac{X^2}{1-X} +aX.$$ Manipulate this to $$f(X) = \frac{X^2}{(1-X)(1-2X)} + \frac{aX}{1-2X}$$ $$= \frac{1}{2} + \frac{1/2}{1 - 2X} - \frac{1}{1-X} + \frac{aX}{1-2X}$$ $$=\frac{1}{2} + \sum_{n=0}^{\infty} 2^{n-1} X^n - \sum_{n=0}^{\infty} X^n + \sum_{n=1}^{\infty} 2^{n-1}a X^n$$ $$= 0 + \sum_{n=1}^{\infty} (2^{n-1} - 1 + 2^{n-1}a) X^n$$ and comparing coefficients gives $T(n) = 2^{n-1} - 1 + 2^{n-1}a.$