Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
1  
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
add comment

2 Answers

up vote 2 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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.