<s>[INST] Solve the recurrence relation $a_n = 2a_{n-1} + 2^n$ with $a_0 = 1$ using generating functions 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.
 [/INST] 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$$
</s>