Using a generating function to solve a recursion I know that the generating function for the sum of Fibonacci numbers with even index is
\begin{align}
F_e(z)
  &= \sum_{n \ge 0} F_{2 n} z^n \\
  &= \frac{F(z^{1/2}) + F(- z^{1/2})}{2} \\
  &= \frac{z}{1 - 3 z + z^2} \\
\end{align}
I read that we can use this to solve recurrence relations, for e.g. I consider the recurrence $g_0=1$, $g_n=g_{n-1}+2g_{n-2}+...+ng_0$. But I don't know how generating functions are used in this manner.
 A: 
LEMMA:
Let $$A(x)=\sum_{n=0}^{\infty}a_nx^n=\frac{P(x)}{Q(x)}$$ where $P(x)$ and $Q(x)$ are  polynomials with degQ $>$ degP , and  $Q(x)=1+\alpha_1x+\alpha_2x^2+\alpha_3x^3+\alpha_4x^4+...+\alpha_qx^q$
Then , $$a_{q+n}+\alpha_1a_{q+n-1}+\alpha_2a_{q+n-2}+\alpha_3a_{q+n->3}+...\alpha_qa_{q}=0,n \geq0$$

According to this lemma , $Q(x)=1-3x+x^2$ , then $\alpha_1=-3, \alpha_2=1$.
Result , $$a_{n+2}-3a_{n+1}+a_{n}=0 \rightarrow a_n=3a_{n-1}-a_{n-2} , a_1=1 ,a_2=3$$
A: The key idea here is the generating function of a product.
If
$$ A(x)\!:=\!a_0\!+\!a_1x\!+\!a_2x^2\!+\cdots,\;
B(x)\!:=\!b_0\!+\!b_1x\!+\!b_2x^2\!+\!\cdots, $$ then
$$ A(x)B(x) = (a_0b_0)+(a_0b_1+a_1b_0)x+
(a_0b_2+a_1b_1+a_2b_0)x^2+\cdots. $$
In your case, you need to know that
$$ \frac{x}{1-2x+x^2} = 1x+2x^2+3x^3+4x^4\cdots. $$
Apply this to $\,G(x):=g_0+g_1x+g_2x^2+\cdots\,$ to get
$$ G(x)\frac{x}{1\!-\!2x\!+\!x^2} \!=\!
(1g_0)x\!+\!(1g_1+2g_0)x^2\!+\!
(1g_2+2g_1+3g_0)x^3+\cdots.$$
Substitute the given information
$$ g_0=1,\;\;g_n=g_{n-1}+2g_{n-2}+...+ng_0 $$
to get
$$ G(x)\frac{x}{1\!-\!2x\!+\!x^2} \!=\!
g_1x+g_2x^2+g_3x^3+\cdots = -1+G(x) $$
and solve the equation for $\,G(x).$
