In an algorithm I'm developing for one of my computer science classes, I need to find the general formula for each term of the sequence $T_n$. This sequence is defined in the following way:
Define the sequences $b_n$ and $p_n$ as:
- $p_1 = 1$ and $b_1 = 0$
- $p_{n+1} = 2\cdot p_n$
- $b_{n+1} = 2\cdot b_n + p_n$
Then, we define $T_n = b_n + p_n$
It's easy to see that $p_n = 2^{n-1}$, so we get the following recursion relation for $b_n$: $$b_{n+1} = 2\cdot b_n + 2^{n-1}$$
But now I'm having some trouble finding the formula for $b_n$ because of that $2^{n-1}$ term.
How can this be done? I always have some trouble finding formulas for sequences given a recurrence relation, so I would appreciate some general advice/techniques for solving this kind of problem.
Best Answer
One of the (probably, the) most important techniques for finding explicit formulae for sequences defined by recurrences is that of generating functions. (In this case it might be overkill but it is worth learning it at some point in my opinion.)
The idea is (1) to define the formal power series $$ B(x)=\sum_{n\geq 1} b_{n} x^{n}, \qquad\qquad \mbox{(the "generating function")} $$
(2) to translate the recurrence into some equation for $B(x)$, (3) to solve this equation for $B(x)$, and, finally, (4) to re-expand $B(x)$ to get the answer.
In this case, take the recurrence $$ b_{n+1}=2b_n+2^{n-1}, $$ multiply it by $x^{n+1}$ and sum over $n\geq 1$ to obtain a relation about the generating function $B(x)$. Proceeding separately for each term in the recurrence, we have \begin{align*} \sum_{n\geq 1}b_{n+1}x^{n+1} &= b_2x^2+b_3x^3+\cdots=B(x)-b_1x=B(x), \\ \sum_{n\geq 1}2b_{n}x^{n+1}&=2xB(x), \\ \sum_{n\geq 1}2^{n-1}x^{n+1}&=\frac{x^2}{1-2x}. \end{align*} In the first equality we used that $b_1=0$ by assumption (but the method would work for any value of $b_1$), and in the third equality a geometric series. Collecting these pieces, the recurrence for the coefficients is equivalent to the (algebraic, in this case) relation $$ B(x)=2xB(x)+\frac{x^2}{1-2x}. $$ We can solve for $B(x)$: $$ B(x)=\frac{x^2}{(1-2x)^2}. $$ The final step consists in re-expanding in Taylor series $B(x)$ to read off the coefficients. With some experience you recognize that here you need the expansion $$ \frac y{(1-y)^2}=\sum_{n\geq 1}ny^n. $$ (This is, essentially, a derivative of the geometric series $\frac 1{1-y}=\sum_{n\geq 0}y^n$.) Apply it with $y=2x$ to get $$ B(x)=\frac x2\frac {(2x)}{(1-2x)^2}=\frac x2\sum_{n\geq 1}n(2x)^n= \sum_{n\geq 1}n2^{n-1}x^{n+1}=\sum_{n\geq 1}(n-1)2^{n-2}x^{n} $$ finally yielding the desired answer $$ b_n=(n-1)2^{n-2}. $$
A good reference (but there are plenty) for this method is
Wilf: Generatingfunctionology (available at https://www2.math.upenn.edu/~wilf/DownldGF.html)