Assume that $(a_n)^{\infty}_{n=0}$ is a sequence given by $a_0=1$ and $a_{n+1}=2a_{n}+n$ for all $n \ge 0$, what is the formula for $a_n$? Assume that $(a_n)^{\infty}_{n=0}$ is a sequence given by $a_0=1$ and $a_{n+1}=2a_{n}+n$ for all $n \ge 0$, what is the formula for $a_n$?
we know that $F(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots$
and our sequence is $1, 2, 5, 12, 27, 58, \dots$
to find the generating function for the sequence I started with
$F(x)=a_0+(\underline{2a_0}+\widetilde0)x+(\underline{2a_1}+\widetilde1)x^2+(\underline{2a_2}+\widetilde2)x^3+\dots$
after distributing the variables into the parenthesis, i separated the terms with $\underline{}$ and $\widetilde{}$
$\underline{} = 2a_0x+2a_1x^2+2a_2x^3+2a_3x^4+\dots$
$\underline{} = 2x(a_0+a_1x^1+a_2x^2+a_3x^3+\dots)$
$\underline{} = 2x \times F(x)$  
$\widetilde{} = x^2 + 2x^3 + 3x^4 + 4x^5$
now I don't know what to do with this part, if I had used $n$ earlier instead of putting in the numbers I could just factor out $nx^2$ and get $\widetilde{} = nx^2(\frac{1}{1-x})$ but I don't think I can have $n$ when solving for the generating function of the sequence?
Any ideas of how to get past just this part?
 A: From the recursion formula, you can guess a linear combination of $a_n$ and $n$ will be a geometric sequence, that is, you can assume $a_{n+1}-\lambda(n+1)+M=2(a_n-\lambda n+M)$ for some $\lambda$ and $M$. Put it into the the recursion formula, we can take $\lambda=-1$ and $M=1$. So we get 
$$a_{n+1}+(n+1)+1=2(a_n+n+1).$$
Let $b_n=a_n+n+1$, then $b_{n+1}=2b_n$, which implies that $b_n=2^nb_0$. Since $b_0=a_0+0+1=2$, then $b_n=2^{n+1}$, which implies that 
$$a_n=b_n-n-1=2^{n+1}-n-1.$$
A: My preferred approach using generating functions starts by assuming that $a_n=0$ for $n<0$ and rewriting the recurrence so that it hold for all $n\ge 0$:
$$a_n=2a_{n-1}+n-1+2[n=0]\;.\tag{1}$$
Here $[n=0]$ is an Iverson bracket, and the last term of $(1)$ ensures that $a_0=1$. Now multiply $(1)$ by $x^n$ and sum over $n\ge 0$; if we let $g(x)=\sum_{n\ge 0}a_nx^n$ be the generating function, we have
$$\begin{align*}
g(x)&=\sum_{n\ge 0}a_nx^n\\
&=2\sum_{n\ge 0}a_{n-1}x^n+\sum_{n\ge 0}nx^n-\sum_{n\ge 0}x^n+2\\
&=2x\sum_{n\ge 0}a_nx^n+x\sum_{n\ge 0}nx^{n-1}-\frac1{1-x}+2\\
&=2xg(x)+\frac{x}{(1-x)^2}-\frac1{1-x}+2\;.
\end{align*}$$
Solving for $g(x)$, decomposing the resulting rational function into partial fractions, and rewriting the resulting terms as formal power series, we get
$$\begin{align*}
g(x)&=\frac{x}{(1-x)^2(1-2x)}-\frac1{(1-x)(1-2x)}+\frac2{1-2x}\\
&=\frac{x-(1-x)+2(1-x)^2}{(1-x)^2(1-2x)}\\
&=\frac{1-2x+2x^2}{(1-x)^2(1-2x)}\\
&=\frac2{1-2x}-\frac1{(1-x)^2}\\
&=2\sum_{n\ge 0}(2x)^n-\sum_{n\ge 0}(n+1)x^n\\
&=\sum_{n\ge 0}\left(2^{n+1}-n-1\right)x^n\;,
\end{align*}$$
which yields the closed form
$$a_n=2^{n+1}-n-1\;.$$
A: You must note that $a_0=1$ which is unaccounted for...
Using the fact that 
$$\frac{d}{dx}\left(\frac{1}{1-x}\right)=\frac{1}{(1-x)^2}=1+2x+3x^2+...$$
you now should get
$$F(x)=1+2xF(x)+x^2\frac{1}{(1-x)^2}$$
$$F(x)(1-2x)=1+\frac{x^2}{(1-x)^2}$$
$$F(x)=\frac{1-2x+2x^2}{(1-2x)(1-x)^2}$$
Now use partial fraction decomposition to obtain three power series and look at the coefficients.
