Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Best to ask by example. Given the recurrence relation $a_{n}=a_{n-1}+a_{n-2}$, and some given initial conditions, we can find a similar relation for the generating function for the sequence, $f(x)=\sum_{n=0}^\infty a_nx^n$: $$f(x)=xf(x)+x^2f(x)+c(x)$$ Where $c(x)$ is a polynomial encoding the initial conditions. My main question is how can this polynomial be computed as painlessly as possible from the initial conditions? This is interesting not only for Fibonacci but in general, of course.

A similar, probably equivalent questions is this: If for some sequence we have a rational generating function $\frac{p(x)}{q(x)}$ then the coefficients of $q(x)$ are exactly the coefficients of the recurrence relation for the sequence. Also, $p(x)$ is dependent on the initial conditions - but again, it's not clear to me how to compute those initial conditions from $p(x)$.

share|cite|improve this question
I added the $x^n$ that you left out of the generating function. – Brian M. Scott Dec 19 '11 at 8:10
We know $f(0)$ and $f'(0)$. That's enough to determine $c(x)$. – André Nicolas Dec 19 '11 at 8:12
André, I'm not sure I understand. Would you like to elaborate in an answer? – Gadi A Dec 19 '11 at 8:47
up vote 7 down vote accepted

If your initial conditions are $a_0$ and $a_1$, $p(x)=c(x)=(a_1-a_0)x+a_0$. Look at it this way. You have $$a_n=a_{n-1}+a_{n-2}\tag{1}$$ for $n\ge 2$. Assume that $a_n=0$ for $n<0$. Then $(1)$ is valid for all integers $n$ except possibly $0$ and $1$. To make it valid for all integers, add a couple of terms using the Iverson bracket to get $$a_n=a_{n-1}+a_{n-2}+(a_1-a_0)[n=1]+a_0[n=0]\;.\tag{2}$$

Note that while $a_0$ is straightforward, you have to be careful for $n>0$, since the earlier initial values are automatically built into the basic recurrence.

Now multiply $(2)$ through by $x^n$ and sum:

$$\begin{align*} \sum_na_nx^n&=\sum_na_{n-1}x^n+\sum_na_{n-2}x^n+(a_1-a_0)\sum_n[n=1]x^n+a_0\sum_n[n=0]x^n\\ &=x\sum_na_nx^n+x^2\sum_na_nx^n+(a_1-a_0)x+a_0\;. \end{align*}$$

Thus, if your generating function is $A(x)=\displaystyle\sum_na_nx^n$, you have $$A(x)=xA(x)+x^2A(x)+(a_1-a_0)x+a_0\;,$$ and hence $$A(x)=\frac{(a_1-a_0)x+a_0}{1-x-x^2}\;.$$

This obviously generalizes to higher-order recurrences and other starting points for the initial values. For example, a third-order recurrence with initial values $a_0,a_1,a_2$ would have

$$\begin{align*} p(x)=c(x)&=a_0+(a_1-a_0)x+\left(a_2-\big(a_0+(a_1-a_0)\big)\right)x^2\\ &=a_0+(a_1-a_0)x+(a_2-a_1)x^2\;. \end{align*}$$

In general with initial values $a_0,\dots,a_m$ you’ll get Iverson terms


in the recurrence and


share|cite|improve this answer
Your $c(x)$ is incorrect because (2) does not hold for $n=1$. As a consequence, the ratio $(a_1x+a_0)/(1-x-x^2)$ is $a_0+(a_1+a_0)x+$higher terms and not $a_0+a_1x+$higher terms. – Did Dec 19 '11 at 8:30
As pointed out, this naive c(x) is tempting but incorrect. I had the same mistake myself, and this is the reason I'm asking the question. – Gadi A Dec 19 '11 at 8:44
For example (copied my from Sage): sage: f(x) = (x+1)/(1-x-x^2) sage: f.taylor('x', 0, 5) x |--> 13*x^5 + 8*x^4 + 5*x^3 + 3*x^2 + 2*x + 1 – Gadi A Dec 19 '11 at 8:45
@Didier: Fixed. Not the first time I’ve done that; you’d think that I’d know better by now. (I’ve worked too many classroom examples with $a_0=0$, I think!) – Brian M. Scott Dec 19 '11 at 9:01

Look at a slightly more general problem $a_n=pa_{n-1}+qa_{n-2}$. As in your Fibonacci case, we get $$f(x)=pxf(x)+qx^2f(x)+c(x).$$ Since $f(0)=a_0$, we have $c(0)=a_0$. Now differentiate, and note that $a_1=f'(0)$. (In general, $a_n n!=f^{(n)}(0)$.)

We get $$f'(x)=pxf'(x)+pf(x)+qx^2f'(x)+2qxf(x)+c'(x),$$ so $$c'(0)=f'(0)-pf(0)=a_1-pa_0.$$ Since everything is determined once $a_0$ and $a_1$ are known, $c(x)$ is a polynomial of degree $\le 1$, and therefore $c(x)=c'(0)x+c(0)=(a_1-pa_0)x+a_0$.

Repeated differentiation also has to work for your more general question, since the derivatives at $0$ determine the coefficients.

share|cite|improve this answer

If you have: $$ A(z) = \sum_{n \ge 0} a_n z^n $$ then also: $$ \frac{A(z)}{1 - z} = \sum_{n \ge 0} \left(\sum_{0 \le k \le n} a_k \right) z^n $$ (multiply out, the inner sums telescope away leaving just the last terms).

share|cite|improve this answer

General technique is to write your recurrence so there are no subtractions in indices:

$$ a_{n + 2} = a_{n + 1} + a_n $$

Multiply by $z^n$, sum over $n \ge 0$:

$$ \sum_{n \ge 0} a_{n + 2} z^n = \sum_{n \ge 0} a_{n + 1} z^n + \sum_{n \ge 0} a_n z^n $$

Recogize some sums:

$$ \frac{A(z) - a_0 - a_1 z}{z^2} = \frac{A(z) - a_0}{z} + A(z) $$

If you solve this for $A(z)$, you get a rational function in $z$. The numerator encodes the initial values, the denominator depends only on the recurrence.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.