The Fibonacci numbers are defined by the equations $F_{0}=0, F_{1}=1$ and $F_{n+1}=F_{n}+F_{n-1}$ for any positive integer $n$. Show that the highest common factor $\left(F_{n+1}, F_{n}\right)$ is $1 .$

Let $n$ be a natural number. Prove by induction on $k$ that for all positive integers $k$,

$$F_{n+k}=F_{k} F_{n+1}+F_{k-1} F_{n} .$$

Deduce that $F_{n}$ divides $F_{n l}$ for all positive integers $l$. Deduce also that if $m \geq n$ then

$$\left(F_{m}, F_{n}\right)=\left(F_{m-n}, F_{n}\right) .$$