Copyright © University of Cambridge. All rights reserved.
'Fibonacci Fashion' printed from https://nrich.maths.org/
Here is another excellent solution from Andrei of Tudor Vianu
National College, Bucharest, Romania.
We are given $F_n={1\over\sqrt5}(\alpha^n-\beta^n)$ where $\alpha$
and $\beta$ are solutions of the quadratic equation $x^2-x-1=0$ and
$\alpha > \beta$.
(1) In the quadratic equation $ax^2+bx+c=0$ with roots $\alpha$ amd
$\beta$, using Viete's relations for the sum and product of the
roots, I obtain: $\alpha\beta =-b/a$, $\alpha + \beta = c/a$
In the particular case of the equation $x^2-x-1=0$, I have:
$\alpha\beta =-1$, $\alpha + \beta = 1$
(2)$${1\over \alpha} + {1\over \alpha^2}={\alpha + 1\over
\alpha^2}=1$$ as $\alpha$ satisfies $x^2=x+1$. Similarly for
$\beta$.
(3) Here I shall prove that $F_1=1$, $F_2=1$ and $F_n + F_{n+1} =
F_{n+2}$ and hence $F_n$ is the $n$th Fibonacci number. First, I
calculate $\alpha$ and $\beta$: $\alpha={1+\sqrt5\over 2}$ and
$\alpha={1+\sqrt5\over 2}$
$$\begin{eqnarray} F_1 &= {1\over \sqrt 5}\left( {1+\sqrt 5
\over 2} - {1-\sqrt 5 \over 2}\right) = 1 \\ F_2 &= {1\over
\sqrt 5}(\alpha^2 - \beta^2) = {1\over \sqrt 5} (\alpha -
\beta)(\alpha + \beta) = 1 \\ F_n +F_{n+1}- F_{n+2}&= {1\over
\sqrt 5}[\alpha^n -\beta^n + \alpha^{n+1} -\beta^{n+1} -
\alpha^{n+2} + \beta^{n+2}] \\ F_n + F_{n+1}- F_{n+2}&= {1\over
\sqrt 5}[-\alpha^n(\alpha^2 - \alpha - 1) +\beta^n(\beta^2- \beta
-1)]=0\end{eqnarray}$$
(4) I shall prove by induction the statement $P_n$ that $1 + F_1 +
F_2 + \cdots F_n = F_{n+2}$.
I know that $F_1=1, F_2=1$ and by (3), $F_3=2, F_4=3, F_5=5,
F_6=8,...$\\ For $n=1$, $P_1$ is $1+ F_1 = F_3$ which is evidently
true as 1 + 1 = 2.
For $n=2$, $P_1$ is $1+ F_1 + F_2= F_4$ which is evidently true as
1 + 1 + 1 = 3.
For $n=3$, $P_1$ is $1+ F_1 + F_2 + F_3 = F_5$ which is evidently
true as 1 + 1 + 1 + 2 = 5.
Now I assume that $P(k)$ is true for a fixed $k$ and I shall prove
that $P(k+1)$ is also true, that is:
$$\begin{eqnarray} P_k &: 1 + F_1 + F_2 + \cdots F_k = F_{k+2}
\\ P_{k+1}&: 1 + F_1 + F_2 + \cdots F_k + F_{k+1} =
F_{k+3}\end{eqnarray}$$
$$\begin{eqnarray}1 + F_1 + F_2 + \cdots F_k + F_{k+1}&= (1 +
F_1 + F_2 + \cdots F_k ) + F_{k+1}\\ &= F_{k+2} + F_{k+1} \\
&= F_{k+3}\end{eqnarray}$$
and hence the result is true for $n=k+1$. By the principle of
mathematical induction the statement $P_n$ is true for all positive
integer values of $n$ which completes the proof.