Solve the recurrence relation $a_n = 2a_{n-1} + 2^n$ with $a_0 = 1$ using generating functions

Question

Here is what I have so far, or what I know how to do, rather:

I am given this equation: $a_n = 2a_{n-1} + 2^n$ with $a_0 = 1$

So, with the $2a_{n-1}$, I know I can do the following.

We change the $a_n$ to $x^n$, so then we have $x^n = 2^{n-1}$. When we take away $n-1$ from both sides, we get $x = 2$, and the root is 2.

Then when have $a_n = A_12^n$, with $a_0 = 1$, to which then we do:

$1= a_0 = A_12^0 = A_1 = 1$, and $a_n = 1*2^n$.

But, that is not the correct answer, and I am not sure what to do with the $2^n$ part, which is necessary to get the answer. Could anybody help me? Any help is greatly appreciated.

Answer 1

Let $f(x)=\sum a_nx^n$. Then $$\begin{align} f(x)&=1+\sum_{n=1}^\infty (2a_{n-1}+2^n)x^n\\ &=1+2xf(x) + \frac{2x}{1-2x}\\ &=2xf(x)+\frac{1}{1-2x} \end{align}$$

Solve for $f(x)$ to get a closed form for your generating function, and you should be able to figure out a closed formula for $a_n$ from there.

Answer 2

Let

$$f(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots$$

We know for a fact that $\frac{1}{1-x}=1+x+x^2+\cdots$ so we can compute \begin{align} 2xf(x)+\frac{1}{1-2x}&=2a_0x+2a_1x^2+2a_2x^3+\cdots+1+(2x)+(2x)^2+\cdots\\ &=1+(2a_0+2)x+(2a_1+2^2)x^2+(2a_2+2^3)x^3+\cdots\\ &=a_0+a_1x+a_2x^2+a_3x^3+\cdots\\ &=f(x) \end{align} Now we get a functional equation $2xf(x)+\frac{1}{1-2x}=f(x)$ which we can solve to get $$f(x)=\frac{-1}{(1-2x)(2x-1)}=\frac{1}{(1-2x)^2}=(1-2x)^{-2}$$ and now we make the Taylor series for that, and we see that \begin{align} f(x)&=(1-2x)^{-2}\\ f'(x)&=(-2)(-2)(1-2x)^{-3}=2\cdot2\cdot(1-2x)^{-3}\\ f''(x)&=(-2\cdot2)\cdot(-3\cdot2)\cdot(1-2x)^{-4}=2^2\cdot3!\cdot(1-2x)^{-4}\\ &\vdots\\ f^{(n)}&=2^n\cdot(n+1)!\cdot(1-2x)^{-n-2} \end{align} so that the coefficients in the Taylor series are $a_n=\frac{f^{(n)}(0)}{n!}=(n+1)2^n$. So we get $$a_n=(n+1)2^n$$