Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Suppose I know the generating function.Then how do I find out the dependence of of the $n^{\text{th}}$ term on the past $k$ terms from it??

For eg : Suppose I have the Fibonacci series . I know its $\text{G.F} =x / (1 - x - x^2)$

I can find out that $F(n)=F(n-1)+F(n-2)$

Is it possible to do this in general ?

share|cite|improve this question
up vote 4 down vote accepted

The generating function for the Fibonacci numbers with their usual indexing is actually $$g(x)=\frac{x}{1-x-x^2}\;.$$ You can reverse the process by which it’s obtained from the recurrence. First you get $$\left(1-x-x^2\right)g(x)=x$$ and then $$g(x)=xg(x)+x^2g(x)+x\;.\tag{1}$$ Now write $$g(x)=\sum_{k\ge 0}a_kx^k$$ and substitute into $(1)$:

$$\sum_{k\ge 0}a_kx^k=x\sum_{k\ge 0}a_kx^k+x^2\sum_{k\ge 0}a_kx^k+x\;.$$

Move everything inside the summations, and then shift the indices so that the powers of $x$ match:

$$\begin{align*} &\sum_{k\ge 0}a_kx^k=\sum_{k\ge 0}a_kx^{k+1}+\sum_{k\ge 0}a_kx^{k+2}+x\;,\text{ then}\\\\ &\sum_{k\ge 0}a_kx^k=\sum_{k\ge 1}a_{k-1}x^k+\sum_{k\ge 2}a_{k-2}x^k+x\;. \end{align*}$$

Now make the blanket assumption that $a_k=0$ for all $k<0$, so that you can rewrite that last line with the summations all starting at $0$, and combine summations:

$$\begin{align*} \sum_{k\ge 0}a_kx^k&=\sum_{k\ge 0}a_{k-1}x^k+\sum_{k\ge 0}a_{k-2}x^k+x\\ &=\sum_{k\ge 0}\big(a_{k-1}+a_{k-2}+[k=1]\big)x^k\;, \end{align*}$$

where $[k=1]$ is an Iverson bracket. Finally, strip off the summations:


There you have the basic recurrence and enough information to reconstruct the initial data. From the blanket convention that $a_k=0$ for $k<0$ you get $a_0=a_{-1}+a_{-2}+[0=1]=0$, and then from $(2)$ you get $a_1=a_0+a_{-1}+[1=1]=0+0+1=1$. For $k>1$ the bracket term is $0$, and you have just the familiar Fibonacci recurrence.

This should work whenever the generating function is a rational function.

share|cite|improve this answer
Thank You..your good and clear explanation made it so easy :) – Wayne Rooney Nov 6 '12 at 14:49
@Wayne: You’re welcome. – Brian M. Scott Nov 6 '12 at 14:53

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.