Past exam of the mathematics course of the University of Cambridge / 2003 / ia / Paper 4 / 7C / i / Solution

Write $F_n=x_n$. For $n\ge 1$, the recurrence and the previously proved greatest common divisor invariance giveRepeating reaches $\gcd (F_1,F_0)=\gcd (1,0)=1$. This also gives the $n=0$ case directly. Applying the same invariance once more,Thus both requested greatest common divisors equal one for every $n\ge 0$. This is the adjacent-index instance of Fibonacci gcd reduction, derived directly rather than assuming the stronger general formula.