3
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for the confirmation that I'm heading in the right direction. Your comment made me realize that I should probably just do another PFD on that first term, after finding the roots of x^2+x-1. I will give that a try, thanks! $\endgroup$
    – Nate
    Commented Apr 20, 2014 at 6:42
1
$\begingroup$

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}

$\endgroup$
3
  • $\begingroup$ I was going to post an answer suggesting this "simpler way", but I feel the OP's way actually turns out to be simpler here. $\endgroup$ Commented Apr 21, 2014 at 3:56
  • $\begingroup$ @ShreevatsaR, I believe my technique is more general. $\endgroup$
    – vonbrand
    Commented Jul 27, 2015 at 1:11
  • $\begingroup$ I agree; that's part of why it's less simple in this case. $\endgroup$ Commented Jul 27, 2015 at 4:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .