Recurrence relation with generating function problem

Question

I've got a recurrence problem that I'm close to solving, but having trouble with finishing up.

Solve the following recurrence relation using generating functions: $$g_n = g_{n-1} + g_{n-2} + n$$ for $ n>=2, g_0 = 1, g_1 =2 $.

What I've done so far:

$$G(x) = \sum_{n=0}^{\infty}g_nx^n$$ $$g_n < 0 = 0$$ Changed $g_n$ to work for all $n >= 0$: $$g_0 = 1 = g_{n-1} + g_{n-2} + n + [n=0] $$

$[n=0]$ is conditional on whether n is 0. This makes $g_n$ work for $g_0$ and $g_1$.

I want it in the form of $G(x)$, so I multiply by $x^n$ and sum over $x>=0$:

$$\sum_{n=0}^{\infty}g_nx^n = \sum_{n=0}^{\infty}g_{n-1}x^n +\sum_{n=0}^{\infty}g_{n-2}x^n + \sum_{n=0}^{\infty}nx^n + \sum_{n=0}^{\infty}[n=0]x^n$$

Factor $x$ out of the first term on the right, and $x^2$ from the second. Third is rewritten, and the final term is just 1.

$$G(x) = xG(x) +x^2G(x)+ \frac{x}{(x-1)^2}+1 $$

Solving for $G(x)$:

$$G(x) = \frac{-x^2+x-1}{(x-1)^2(x^2+x-1)}$$

This is the point at which I'm stuck. From what I've understood from lecture, I want to do a partial fraction decomposition with the parts in the form $1/(1-x)$, so they can be expressed as $\sum_{n=0}^{\infty}px^n$ so that I can extract the coefficients to create the closed formula. Once I have them in that form, I know how to proceed. I've gotten this PFD, but I can't seem to figure out how to get it in the right form:

$$\frac{-2x-4}{x^2+x-1}+\frac{2}{x-1}-\frac{1}{(x-1)^2}$$

So either I've messed up somewhere in the problem, or I'm missing something on how to get this in the right form. Thanks for any suggestions.

Answer 1

Everything's fine so far. Hint: find the roots of the polynomial $x^2 + x - 1$.

Answer 2

A simpler way to set this kind of problems up is to write the recurrence with no subtraction in indices: $$ g_{n + 2} = g_{n + 1} + g_n + n + 2 $$ Multiply by $x^n$, sum over $n \ge 0$, and recognize: \begin{align} \sum_{n \ge 0} a_{n + k} x^k &= \frac{G(x) - g_0 - g_1 z - \ldots - g_{k - 1} x^{k - 1}}{x^k} \\ \sum_{n \ge 0} x^n &= \frac{1}{1 - x} \\ \sum_{n \ge 0} n x^n &= x \frac{\mathrm{d}}{\mathrm{d} x} \frac{1}{1 - x} \end{align} and get: $$ \frac{G(x) - 1 - 2 x}{x^2} = \frac{G(x) - 1}{x} + G(x) + \frac{x}{(1 - x)^2} + 2 \frac{1}{1 - x} $$ which gives: \begin{align} G(x) &= \frac{1 - x + x^2}{(1 - x)^2 (1 - x - x^2)} \\ &= \frac{4 + 2 x}{1 - x - x^2} - \frac{2}{1 - x} - \frac{1}{(1 - x)^2} \end{align} Mow it comes handy to know that for the Fibonacci numbers $F_n$, defined by $F_0 = 0$, $F_1 = 1$, $F_{n + 2} = F_{n + 1} + F_n$ you have: \begin{align} \sum_{n \ge 0} F_n x^n &= \frac{x}{1 - x - x^2} \\ \sum_{n \ge 0} F_{n + 1} x^n &= \frac{1}{1 - x - x^2} \end{align} and using: $$ \binom{-2}{n} = (-1)^n \binom{n + 2 - 1}{2 - 1} = (-1)^n (n + 1) $$ you get: \begin{align} g_n &= 4 F_{n + 1} + 2 F_n - 2 - (n + 1) \\ &= 2 F_{n + 2} + 2 F_{n + 1} - n - 3 \\ &= 2 F_{n + 3} - n - 3 \end{align}