Hi guys,
Could you please walk me through this example, as I am struggling with this topic?
Many thanks in advance.
Banana1
http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf
excellent intro to generating functions, as well as advanced discussion.
Hello Banana1Starting 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.
Grandad