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


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

  • $\begingroup$ Ummm... could you be more explicit? I just double-checked my quadratic formula, and it yields the roots in my answer... $\endgroup$ – apnorton Mar 14 '13 at 13:54
  • $\begingroup$ 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. ;-) $\endgroup$ – Jean-Claude Arbaut Mar 14 '13 at 13:56
  • $\begingroup$ Doh! Thanks. :) $\endgroup$ – apnorton 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


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

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.