generating function and lucas numbers Defines the sequence $l$.
$l_n = l_{n−1} + l_{n−2}$, for all $n \ge 2$.
So the ﬁrst few members of the sequence are: $2, 1, 3, 4, 7, 11, 18\;.$
Find the generating function for this sequence and deduce the following formula 
$$l_n =\left(\frac{1 − \sqrt5}2\right)^n +\left(\frac{1 + \sqrt5}2\right)^n\;.$$
After some calculation I got the generating function
$g(x)={x-2\over x^2+x-1} =2+x+3x^2+4x^3\cdots$

Let $$g(x)=h_0+h_1x+h_2x^2+\cdots+h_nx^n+\cdots$$ $$-xg(x)=-h_0x-h_1x^2-h_2x^3-\cdots-h_nx^{n+1}-\cdots$$ $$-x^2g(x)=-h_0x^2-h_1x^3-h_2x^4-\cdots-h_nx^{n+2}-\cdots.$$ Adding we obtain $$(1-x-x^2)g(x)=h_0+(h_1-h_o)x+(h_2-h_1-h_0)x^2+\cdots.$$ Since $l_0=2$ and $l_1=1$ we now have $$g(x)={2\over 1-x-x^2}-{x\over 1-x-x^2}.$$ Let $1-x-x^2=(1-q_1x)(1-q_2x)$ so that $$g(x)={2-x\over (1-q_1x)(1-q_2x)}$$ where $q_1={1+\sqrt5\over 2}$ and $q_2={1-\sqrt5\over 2}$. Using partial fractions $${2-x\over (1-q_1x)(1-q_2x)}={A\over 1-q_1x}+{B\over 1-q_2x}$$ we obtain $A=1$ and $B=1$. So $${1\over 1-q_1x}+{1\over 1-q_2x}.$$Now using the geometric series we have $$\sum_{n=0}^\infty (q_1x)^n+\sum_{n=0}^\infty (q_2x)^n=\sum_{n=0}^\infty[(q_1)^n+(q_2)^n]x^n.$$ Thus $$l_n =\left(\frac{1 − \sqrt5}2\right)^n +\left(\frac{1 + \sqrt5}2\right)^n\;.$$
