2
$\begingroup$

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 ?

1 Answers 1

4

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.

  • 0
    @Wayne: You’re welcome.2012-11-06