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$
3
$\begingroup$

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

$\endgroup$
  • $\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 Apr 20 '14 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$
  • $\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$ – ShreevatsaR Apr 21 '14 at 3:56
  • $\begingroup$ @ShreevatsaR, I believe my technique is more general. $\endgroup$ – vonbrand Jul 27 '15 at 1:11
  • $\begingroup$ I agree; that's part of why it's less simple in this case. $\endgroup$ – ShreevatsaR Jul 27 '15 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.