I recently asked this question about finding the formula for:
$$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.
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$).