Exercise 4.4.8 (New proof of $L_n = \lambda^n + \mu^n$ ($\lambda, \mu$ roots of $x^2 - x -1$))

Proof.

(a)

By definition of these two sequences, $$\begin{array}{llll}\hfill & F_0=0,F_1=1,\forall <!--\; FUNCTION\; APPLICATION\; -->n\in \mathbb{N},F_{n+2}=F_{n+1}+F_n,& \hfill & \\ \hfill & L_0=2,L_1=1,\forall <!--\; FUNCTION\; APPLICATION\; -->n\in \mathbb{N},L_{n+2}=L_{n+1}+L_n.& \hfill & \end{array}$$

We prove by induction on $n\ge 1$ the property

$$𝒫(n):L_n=F_{n-1}+F_{n+1}.$$

• $F_0+F_2=1=L_1$ , and $F_1+F_3=3=L_2$, so $𝒫(1)$ and $𝒫(2)$ are true.

• Suppose now that for some $n\ge 1$, $𝒫(n)$ and $𝒫(n+1)$ are true, so that

  $$L_n=F_{n-1}+F_{n+1},L_{n+1}=F_n+F_{n+2}.$$

  Then

  $$\begin{array}{llll}\hfill L_{n+2}& =L_n+L_{n+1}& \hfill & \\ \hfill & =(F_{n-1}+F_{n+1})+(F_n+F_{n+2})& \hfill & \\ \hfill & =(F_{n-1}+F_n)+(F_{n+1}+F_{n+2})& \hfill & \\ \hfill & =F_{n+1}+F_{n+3}.& \hfill & \end{array}$$

  This shows that $𝒫(n+2)$ is true, and the induction is done.

• In conclusion,

  $$\forall <!--\; FUNCTION\; APPLICATION\; -->n\in {\mathbb{N}}^{\text{∗}},L_n=F_{n-1}+F_{n+1}.$$

(b)

With the same notations as in the preceding problems, $$\lambda =\frac{1-\sqrt{5}}{2},\mu =\frac{1+\sqrt{5}}{2},$$

We know by (4.6) that for all $n\in \mathbb{N}$,

$$F_n=\frac{{\mu }^n-{\lambda }^n}{\mu -\lambda }.$$

Since $\lambda ,\mu$ are the roots of $x^2-x-1$,

$$\mathit{\lambda \mu }=-1.$$

By part (a), for all $n\ge 1$,

$$\begin{array}{llllll}\hfill L_n& =F_{n-1}+F_{n+1}& \hfill & & \hfill & \\ \hfill & =\frac{{\mu }^{n+1}-{\lambda }^{n+1}+{\mu }^{n-1}-{\lambda }^{n-1}}{\mu -\lambda }& \hfill & & \hfill & \\ \hfill & =\frac{(\mu -\lambda )({\lambda }^n+{\mu }^n)+(1+\mathit{\mu \lambda })({\mu }^{n-1}-{\lambda }^{n-1})}{\mu -\lambda }& \hfill & & \hfill & \\ \hfill & =\frac{(\mu -\lambda )({\lambda }^n+{\mu }^n)}{\mu -\lambda }& \hfill (\text{since }\mathit{\lambda \mu }=-1)& & \hfill & & \hfill \\ \hfill & ={\lambda }^n+{\mu }^n.& \hfill & & \hfill & \end{array}$$

This shows anew (4.7):

$$L_n={\lambda }^n+{\mu }^n={\left(\frac{1+\sqrt{5}}{2}\right)}^n+{\left(\frac{1-\sqrt{5}}{2}\right)}^n(n\in {\mathbb{N}}^{\text{∗}}).$$