[ Recurrence relations (other)] Fibonacci numbers $\quad]$

a) Find the generating function of the Lucas number sequence (the definition of Lucas numbers see in problem 60585)

b) Using this function, express $L_{n}$ in terms of $\varphi$ and $\hat{\varphi}$ (see problem $\left.\underline{61502}\right)$.

#
a) According to problem $\underline{60498}$, the generating function $F(x)$ of the Fibonacci number sequence is $\overline{1-x-x^{2}}$

According to problem $\underline{60585}$ a) $L_{n}=F_{n+1}+F_{n-1}$, thus,

$$
L(x)=1+x^{-1} F(x)+x F(x)=1+\frac{1+x^{2}}{x} \cdot \frac{x}{1-x-x^{2}}=\frac{2-x}{1-x-x^{2}}
$$

b) Note that $\frac{1}{1-\varphi x}+\frac{1}{1-\widehat{\varphi} x}=\frac{2-(\varphi+\widehat{\varphi}) x}{(1-\varphi x)(1-\widehat{\varphi} x)}=\frac{2-x}{(1-\varphi x)(1-\widehat{\varphi} x)} \cdot$ Therefore,

$$
L(x)=\frac{1}{1-\varphi x}+\frac{1}{1-\widehat{\varphi} x}, \quad \frac{L^{(n)}(x)}{n!}=\frac{\varphi^{n}}{(1-\varphi x)^{n}}+\frac{\widehat{\varphi}^{n}}{(1-\widehat{\varphi} x)^{n}}, \quad L_{n}=\frac{L^{(n)}(0)}{n!}=\varphi^{n}+\widehat{\varphi}^{n}
$$

## Answer

a) $L(x)=(2-x)\left(1-x-x^{2}\right)^{-1}$; b) $L_{n}=\varphi^{n}+\hat{\varphi}^{n}$.