Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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$

share|cite|improve this answer

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

share|cite|improve this answer
Thank you for the detailed procedure of finding the closed form. Very helpful. Sadly, I can not approve two answers as correct. – John Threepwood Apr 9 '13 at 15:04
@JohnThreepwood That's completely fine. This isn't the most efficient way at solving this problem but I rather like it. – Cocopuffs Apr 9 '13 at 15:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.