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