# How to find out the dependence on past terms from a recurence relation

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 ?

-

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:

$$a_k=a_{k-1}+a_{k-2}+[k=1]\;.\tag{2}$$

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.

-
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