TITLE: Using a generating function to solve a recursion
QUESTION [1 upvotes]: 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.

REPLY [0 votes]: 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).$
{"set_name": "stack_exchange", "score": 1, "question_id": 4456669}