<s>[INST] 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}}$$
 [/INST] $$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})$$
</s>