Copyright © University of Cambridge. All rights reserved.
'Pythagorean Fibs' printed from https://nrich.maths.org/
The Fibonacci sequence is defined by the recurrence relation
(sometimes called 'difference equation') $$F_n + F_{n+1}=F_{n+2}.$$
This is the simplest possible second order recurrence relation with
constant coefficients as all the coefficients are one. The method
of solving recurrence relations like this is to let $F_n=x^n$. Then
$x^n+x^{n+1}=x^{n+2}$ and hence (dividing by $x^n$), $1 + x = x^2$
giving the quadratic equation $x^2-x-1=0$. So the quadratic
equation has solutions $x={1 \pm \sqrt5\over 2}$. Hence the
solutions of the recurrence relation are
$$F_n=A\left({1+\sqrt5\over 2}\right)^n +B \left({1-\sqrt 5\over
2}\right)^n$$ where we have to find the values of the constants $A$
and $B$.
Putting $n=1$ and $F_1 = 1$ and multiplying by 2 $$2 = A(1 + \sqrt
5)+B(1-\sqrt 5)$$ and putting $n=2$ and $F_2=1$ and multiplying by
4 $$ 4 = A(1 + \sqrt 5)^2 + B(1-\sqrt 5)^2.$$ Solving these
simultaneous equations for $A$ and $B$ we get $$A={1\over \sqrt 5},
\quad B =-{1\over \sqrt 5}.$$ Hence the solution of the recurrence
relation is $$F_n = {1\over \sqrt 5}\left({1+\sqrt 5\over
2}\right)^n - {1\over \sqrt 5}\left(1-\sqrt 5\over 2\right)^n.$$
\par Note that the formula for $F_n$ is given in terms of the roots
of the quadratic equation $x^2-x-1=0$ and one of the roots is the
Golden Ratio which accounts for the many connections between
Fibonacci numbers and the Golden Ratio.
This problem complements the material in the article
For a sequence of, mainly more elementary, problems on these
topics see
Golden Mathematics