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$
 A: As is customary, I’ve used $L_n$ for the $n$-th Lucas number rather than $l_n$.
You have 
$$g(x)=\sum_{n\ge 0}L_nx^n=\frac{x-2}{x^2+x-1}\;.$$
It’s a little more convenient to multiply numerator and denominator by $-1$ before splitting into partial fractions:
$$\frac{2-x}{1-x-x^2}=\frac{A}{1-\varphi x}+\frac{B}{1-\widehat\varphi x}\;,$$
where $\varphi=\frac12(1+\sqrt5)$ and $\widehat\varphi=\frac12(1-\sqrt5)$. (You should check that $(1-\varphi x)(1-\widehat\varphi x)$ really is $1-x-x^2$.) Solve for $A$ and $B$ in the usual way: $A(1-\widehat\varphi x)+B(1-\varphi x)=2-x$, so $A+B=2$, and $\widehat\varphi A+\varphi B=1$. This system is easily solved, and we find that $A=B=1$. Thus,
$$g(x)=\frac1{1-\varphi x}+\frac1{1-\widehat\varphi x}\;.$$
Recall that $\frac1{1-u}=\sum_{n\ge 0}u^n$:
$$\sum_{n\ge 0}L_nx^n=g(x)=\sum_{n\ge 0}(\varphi x)^n+\sum_{n\ge 0}(\widehat\varphi x)^n=\sum_{n\ge 0}\varphi^nx^n+\sum_{n\ge 0}\widehat\varphi^nx^n\;.\tag{1}$$
Now just combine the two summations on the right of $(1)$ into a single summation and equate coefficients with the summation on the left of $(1)$ to get your closed form for $L_n$.
A: 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\;.$$
