<s>[INST] 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.
 [/INST] 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.$
</s>