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.