# Using a reverse polynomial for a partial fraction decomposition in a recurrence relation problem

$$gn=g_{n−1}+g_{n−2}+n, g_0=1, g_1=2$$

On that question, I was able to get help to the point of generating this partial fraction decomposition:

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

That question helped me realize to take another PFD of that first term as well. According to my notes, I want the parts in the form $\frac{1}{1-\alpha{x}}$, to be able to generate nice power series. I'm having trouble doing that, though, and getting a proper answer.

My notes have mentioned taking the reverse polynomial, so that I can get the denominator in the form $(1-px)(1-\hat{p}x)$.

Reverse of $x^2+x-2$ is $1+x-x^2$, with factors $\frac{1\pm\sqrt{5}}{2}$. Defining $p = \frac{1+\sqrt{5}}{2}$ and $\hat{p} = \frac{1-\sqrt{5}}{2}$, I can make the PFD:

$$\frac{-2x-4}{(1-px)(1-\hat{p}x)} = \frac{A}{1-px} + \frac{B}{1-\hat{p}x}$$

From which I get $A=\frac{-4}{\sqrt{5}}-2$ and $B = \frac{4}{\sqrt{5}}-2$. Plugging that in:

$$\frac{-2x-4}{(1-px)(1-\hat{p}x)} =\frac{\frac{-4}{\sqrt{5}}-2}{1-px} + \frac{\frac{4}{\sqrt{5}}-2}{1-\hat{p}x}$$

(Pretty nasty looking, I know.) Once I plug that all into my original formula from the previous question, take the series expansion and extract the coefficients, I'm getting a formula that is NOT correct. Did I do that PFD correctly? (The reverse polynomials are making me nervous.)

In particular, the expansion ends up:

$$(\frac{-4}{\sqrt{5}}-2)\sum_{n=0}^{\infty}p^nx^n + (\frac{4}{\sqrt{5}}-2) \sum_{n=0}^{\infty} \hat{p}^nx^n + 2\sum_{n=0}^{\infty}x^n-\sum_{n=0}^{\infty}(n+1)x^n$$

Extracting the coefficients and substituting in $p$ and $\hat{p}$, I get:

$$g(n) = (\frac{-4}{\sqrt{5}}-2)(\frac{1+\sqrt{5}}{2})^n + (\frac{4}{\sqrt{5}}-2)(\frac{1-\sqrt{5}}{2})^n -n + 1$$

That formula clearly doesn't give the right values for $g(n)$. Apparently I was on the right track up until the point of the last question. Did I screw up the PFD in this post, or somewhere else? If someone were able to point out the spot where I'm messing up, that would be greatly appreciated.

• At the very least, you have a minus-sign missing: it's not true that $x^2 + x - 1 = (1-px)(1-\hat{p}x)$, instead $x^2 + x - 1 = -(1-px)(1-\hat{p}x)$. (Another way of seeing it: $x^2 + x - 1$ can't be written in the form $(1-ax)(1-bx)$ as the constant term is different, so we can scale it so that it's right: writing $-(x^2 + x - 1) = (1 - ax)(1 - bx)$ gives $ab = -1$ and $a + b = 1$, so $a$ and $b$ are roots of $t^2 - t -1 = 0$.) – ShreevatsaR Apr 21 '14 at 8:31
• Ah, thanks! I'll give it a try with that correction. – Nate Apr 21 '14 at 8:40

Simpler still: If you define the Fibonacci numbers by $F_0 = 0$, $F_1 = 1$, $F_{n + 2} = F_{n + 1} + F_n$, their generating function is: $$\sum_{n \ge 0} F_n z^n = F(z) = \frac{z}{1 - z - z^2}$$ Also: \begin{align} \sum_{n \ge 0} F_{n + 1} z^n &= \frac{F(z) - F_0}{z} = \frac{1}{1 - z - z^2} \\ \sum_{n \ge 0} F_{n + 2} z^n &= \frac{F(z) - F_0 - F_1 z}{z^2} = \frac{1 + z}{1 - z - z^2} \\ \sum_{n \ge 0} F_{n + 3} z^n &= \frac{F(z) - F_0 - F_1 z - F_2 z^2}{z^3} = \frac{2 + z}{1 - z - z^2} \end{align} Thus you recognize: $$[z^n] \frac{4 + 2 z}{1 - z - z^2} = 2 F_{n + 3}$$ (could also have split into $\frac{1}{1 - z - z^2}$ and $\frac{z}{1 - z - z^2}$, and thus $F_{n + 1}$ and $F_n$).