Paper 4, Section II, E

Numbers and Sets | Part IA, 2010

The Fibonacci numbers FnF_{n} are defined for all natural numbers nn by the rules

F1=1,F2=1,Fn=Fn1+Fn2 for n3F_{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 kk that, for any nn,

Fn+k=FkFn+1+Fk1Fn for all k2F_{n+k}=F_{k} F_{n+1}+F_{k-1} F_{n} \text { for all } k \geqslant 2 \text {. }

Deduce that

F2n=Fn(Fn+1+Fn1) for all n2F_{2 n}=F_{n}\left(F_{n+1}+F_{n-1}\right) \quad \text { for all } n \geqslant 2

Put L1=1L_{1}=1 and Ln=Fn+1+Fn1L_{n}=F_{n+1}+F_{n-1} for n>1n>1. Show that these (Lucas) numbers LnL_{n} satisfy

L1=1,L2=3,Ln=Ln1+Ln2 for n3L_{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 nn, the greatest common divisor (Fn,Fn+1)\left(F_{n}, F_{n+1}\right) is 1 , and that the greatest common divisor (Fn,Ln)\left(F_{n}, L_{n}\right) is at most 2 .

Typos? Please submit corrections to this page on GitHub.