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 ? 
 A: 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.
