Fibonacci Fashion

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.