0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$.) $\endgroup$ – ShreevatsaR Apr 21 '14 at 8:31
  • $\begingroup$ Ah, thanks! I'll give it a try with that correction. $\endgroup$ – Nate Apr 21 '14 at 8:40
1
$\begingroup$

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$).

| cite | improve this answer | |
$\endgroup$

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.