Numbers and Sets | Part IA, 2005

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

Let nn be a natural number. Prove by induction on kk that for all positive integers kk,

Fn+k=FkFn+1+Fk1Fn.F_{n+k}=F_{k} F_{n+1}+F_{k-1} F_{n} .

Deduce that FnF_{n} divides FnlF_{n l} for all positive integers ll. Deduce also that if mnm \geq n then

(Fm,Fn)=(Fmn,Fn).\left(F_{m}, F_{n}\right)=\left(F_{m-n}, F_{n}\right) .

Typos? Please submit corrections to this page on GitHub.