Q:

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.

A:

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:

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.$

