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.
$\begingroup$
$\endgroup$
5
asked Apr 9, 2013 at 14:24
-
2$\begingroup$ 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. $\endgroup$– JulienApr 9, 2013 at 14:27
-
$\begingroup$ @julien: this is more of an answer than a comment, don't you think? $\endgroup$– Ron GordonApr 9, 2013 at 14:48
-
1$\begingroup$ Consider the recurrence $U(n) = T(n) + 1$. $\endgroup$– Sammy BlackApr 9, 2013 at 14:48
-
$\begingroup$ @RonGordon I seem to be in a commenting mood today... $\endgroup$– JulienApr 9, 2013 at 14:50
-
$\begingroup$ @julien: you know, you can take something for that. $\endgroup$– Ron GordonApr 9, 2013 at 14:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.$
-
$\begingroup$ Thank you for the detailed procedure of finding the closed form. Very helpful. Sadly, I can not approve two answers as correct. $\endgroup$ Apr 9, 2013 at 15:04
-
$\begingroup$ @JohnThreepwood That's completely fine. This isn't the most efficient way at solving this problem but I rather like it. $\endgroup$ Apr 9, 2013 at 15:05
$\begingroup$
$\endgroup$
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$
