Take the 2-minute tour ×
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.

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 fibonaci 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|improve this question

1 Answer 1

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:

$$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.

share|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

 
discard

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.