The Fibonacci numbers $F_{n}$ are defined for all natural numbers $n$ by the rules

$$F_{1}=1, \quad F_{2}=1, \quad F_{n}=F_{n-1}+F_{n-2} \quad \text { for } n \geqslant 3$$

Prove by induction on $k$ that, for any $n$,

$$F_{n+k}=F_{k} F_{n+1}+F_{k-1} F_{n} \text { for all } k \geqslant 2 \text {. }$$

Deduce that

$$F_{2 n}=F_{n}\left(F_{n+1}+F_{n-1}\right) \quad \text { for all } n \geqslant 2$$

Put $L_{1}=1$ and $L_{n}=F_{n+1}+F_{n-1}$ for $n>1$. Show that these (Lucas) numbers $L_{n}$ satisfy

$$L_{1}=1, \quad L_{2}=3, \quad L_{n}=L_{n-1}+L_{n-2} \quad \text { for } n \geqslant 3$$

Show also that, for all $n$, the greatest common divisor $\left(F_{n}, F_{n+1}\right)$ is 1 , and that the greatest common divisor $\left(F_{n}, L_{n}\right)$ is at most 2 .