Past exam of the mathematics course of the University of Cambridge / 2010 / ia / Paper 4 / 5E / Solution

For the Fibonacci addition formula, use mathematical induction on $k$, with the assertion applying to every $n\ge 1$. At $k=2$, $F_{n+2}=F_{n+1}+F_n=F_2{F}_{n+1}+F_1{F}_n$. If the formula holds for some $k\ge 2$ and all $n$, apply it at $n+1$ and use the Fibonacci number recurrence:This is the assertion at $k+1$, completing the mathematical induction. ThusTaking $k=n\ge 2$ gives the doubling identity

For the Lucas numbers, $L_2=F_3+F_1=3$, and $L_3=F_4+F_2=4=L_2+L_1$. For $n\ge 4$, both expressions for earlier Lucas numbers are available, andHence $\boxed{L_1=1,L_2=3,L_n=L_{n-1}+L_{n-2}(n\ge 3)}$. The separate $n=3$ check matters because the defining expression for $L_1$ was given separately.

The Euclidean algorithm and the Fibonacci number recurrence give, for $n\ge 2$,Repeating reduces to $\gcd (F_2,F_1)=1$; the case $n=1$ is immediate. Therefore $\boxed{\gcd (F_n,F_{n+1})=1(n\ge 1)}$.

For $n\ge 2$, $L_n=F_n+2F_{n-1}$, so a common divisor $d$ of $F_n,L_n$ divides both $F_n$ and $2F_{n-1}$. Since $F_n,F_{n-1}$ are coprime, Bézout's identity gives integers $s,t$ with $s{F}_n+t{F}_{n-1}=1$. Multiplying by $2$ shows $d\mid 2$. Conversely any common divisor of $F_n$ and $2$ divides $L_n$. Including $n=1$, this proves the stronger greatest common divisor identity