# 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 $L(x) =\sum_{n=0}^{\infty} l_nx^n$, write this using the first two terms that we've been given as:

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

Then plug in the recurrence relation:

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

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

$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 $x^n$:

$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 $L(x)$:

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

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

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

Then we get the Partial Fractions by equating the denominators:

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

Compare coefficients:

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

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

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

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

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

So we can write $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.