# Thread: Recursions and generating functions

1. ## Recursions and generating functions

Hi guys,

Could you please walk me through this example, as I am struggling with this topic?

Banana1

excellent intro to generating functions, as well as advanced discussion.

3. ## Recursion and Generating Functions

Hello Banana1
Originally Posted by Banana1
Hi guys,

Could you please walk me through this example, as I am struggling with this topic?

Banana1
Starting with $\displaystyle L(x) =\sum_{n=0}^{\infty} l_nx^n$, write this using the first two terms that we've been given as:

$\displaystyle L(x) =2+x+\sum_{n=2}^{\infty}l_nx^n$

Then plug in the recurrence relation:

$\displaystyle L(x) =2+x+\sum_{n=2}^{\infty}(l_{n-1}+l_{n-2})x^n$

Next, separate the summations, taking out powers of $\displaystyle x$ so that the power that's left matches the subscript of the $\displaystyle l_n$ term:

$\displaystyle L(x) =2+x+x\sum_{n=2}^{\infty}l_{n-1}x^{n-1}+x^2\sum_{n=2}^{\infty}l_{n-2}x^{n-2}$

Next, we change the summation limits so that we get terms in $\displaystyle x^n$:

$\displaystyle L(x) =2+x+x\sum_{n=1}^{\infty}l_{n}x^{n}+x^2\sum_{n=0}^ {\infty}l_{n}x^{n}$

Now we can express the summations in terms of the original one for $\displaystyle L(x)$:

$\displaystyle L(x) =2+x+x(L(x)-2)+x^2L(x)$ (That's the clever bit!)

$\displaystyle \Rightarrow L(x)(1-x-x^2)= 2-x$

$\displaystyle \Rightarrow L(x) = \frac{2-x}{1-x-x^2}$

Then we get the Partial Fractions by equating the denominators:

$\displaystyle 1-x-x^2 = (1-ax)(1-bx)$

Compare coefficients:

$\displaystyle \Rightarrow ab = -1, a+b = 1$

So $\displaystyle a$ and $\displaystyle b$ are the roots of $\displaystyle m^2-m-1=0$

Let's say $\displaystyle a = \frac{1+\sqrt5}{2}, b=\frac{1-\sqrt5}{2}$

(So note that $\displaystyle a = \phi$ and $\displaystyle b = 1-\phi$.)

Using the usual Partial Fractions technique gives $\displaystyle A=B=1$

So we can write $\displaystyle L(x) = \frac{1}{1-\phi x}+\frac{1}{1-(1-\phi)x}$

... and I'll leave it to you to see if you can supply the missing working and finish up.