# Generating Functions: Solving a Second-Order Recurrence

I'm self-studying generating functions (using GeneratingFunctionology as a text). I came across this programming problem, which I immediately recognized as a modification of the Fibonacci sequence. I wanted to place my newly found generating function techniques to work, so I tried to solve the recurrence.

The problem basically boils down to solving:

$$a_{n+2} = a_{n+1} + ka_n$$ Where $n \ge 0$, and $k$ is some positive integer. And, $a_0 = 1$, $a_1 = 1$.

However, my solution (below, but not really simplified, since I'm just plugging it into a computer) yields values that too great by a factor of $k$.

My solution:

$$a_n = \frac{r_2^{n+1} - r_1^{n+1}}{(r_2-r_1)r_1^{n+1}r_2^{n+1}}$$ Where: $$r_1 = \frac{-1 - \sqrt{1+4k}}{2k}$$ $$r_2 = \frac{-1 + \sqrt{1+4k}}{2k}$$

If someone could help me understand where I went wrong, I'd much appreciate it. (I don't see why I'm too great by a factor of $k$.)

My work is as below:

$$a_{n+2} = a_{n+1} + ka_n$$ $$\sum_{n\ge0}a_{n+2}x^n = \sum_{n\ge0}a_{n+1}x^n + k\sum_{n\ge0}a_{n}x^n$$

Let $A(x) = \sum_{n\ge0}a_nx^n$. Then:

$$\frac{A(x) - a_0 - xa_1}{x^2} = \frac{A(x) - a_0}{x} + kA(x)$$ $$A(x)\left(\frac{1}{x^2} -\frac{1}{x} - k\right) = \frac{1+x}{x^2} - \frac{1}{x}$$ $$A(x)\left(\frac{1 - x - kx^2}{x^2}\right) = \frac{1}{x^2}$$ $$A(x)= \frac{1}{1 - x - kx^2}$$

Now, factoring the denominator yields two roots, $r_1$ and $r_2$ as denoted above. This, in turn, yields: $$A(x) = \frac{1}{(x-r_1)(x-r_2)}$$ Partial fractions: $$A(x) = \frac{1}{r_2-r_1}\frac{1}{(r_1 - x)} - \frac{1}{r_2-r_1}\frac{1}{(r_2 - x)}$$ $$A(x) = \frac{1}{(r_2-r_1)(r_1)}\frac{1}{(1 - \frac{x}{r_1})} - \frac{1}{(r_2-r_1)(r_2)}\frac{1}{(1 - \frac{x}{r_2})}$$ $$A(x) = \frac{1}{(r_2-r_1)(r_1)}\sum_{n\ge0}{\left(\frac{x}{r_1}\right)^n} - \frac{1}{(r_2-r_1)(r_2)}\sum_{n\ge0}{\left(\frac{x}{r_2}\right)^n}$$

Combining: $$A(x) = \sum_{n\ge0} x^n \left(\frac{1}{(r_2-r_1)(r_1^{n+1})} - \frac{1}{(r_2-r_1)(r_2^{n+1})}\right)$$ Therefore: $$a_n = \frac{r_2^{n+1} - r_1^{n+1}}{(r_2-r_1)r_1^{n+1}r_2^{n+1}}$$

-

Something went wrong between

$$A(x)= \frac{1}{1 - x - kx^2}$$

And

$$A(x) = \frac{1}{(x-r_1)(x-r_2)}$$

-
Ummm... could you be more explicit? I just double-checked my quadratic formula, and it yields the roots in my answer... –  anorton Mar 14 '13 at 13:54
If you develop the denominator of the second equation, you won't get a $k \ x^2$ but a $x^2$ alone. Thus the factor $k$ (actually $-k$). Common mistake, to compute the roots correctly, but forget the leading coefficient in factorization. ;-) –  jca Mar 14 '13 at 13:56
Doh! Thanks. :) –  anorton Mar 14 '13 at 13:57

$$1-x-kx^2=-kx^2-x+1\Rightarrow x_{1,2}=\frac{1\pm\sqrt{1+4k}}{2}$$so

$$1-x-kx^2=-kx^2-x+1=(-k)(x-x_1)(x-x_2)=(-k)(x-\frac{1-\sqrt{1+4k}}{2})(x-\frac{1+\sqrt{1+4k}}{2})$$

-
Almost right :-) Were has gone $k$ ? –  jca Mar 14 '13 at 14:08
which k you mean –  Adi Dani Mar 14 '13 at 14:19
The one before $x^2$... –  jca Mar 14 '13 at 14:21
yes I see now is my mistake, thank you –  Adi Dani Mar 14 '13 at 14:27