An equation for Fibonacci numbers

Question

Let $F(n)$ be $n$-th Fibonacci-number. Then the following holds: $$F(n)^2+F(n+1)^2=F(2n+1).$$ I have proved, but I want a brief proof. Do you know anything about it?

Answer 1

I can do a pretty neat proof ... though it does require a bit of set-up.

In particular, it's easily proven by relating the Fibonacci numbers to the following problem:

Suppose that you want to go up some flight of stairs and at every step you can take either one or two stairs: in how many ways can you get up the stairs?

Well, if we say that there are $n$ stairs, then it turns out there are $F_{n+1}$ ways to do it.

A very easy inductive proof shows why:

Base cases: If there is $1$ stairs, you can do it in only $1$ way, and indeed $F_{1+1}=F_2=1$. If there are $2$ stairs, then there are two ways: either take two steps of $1$, or take one step of $2$. And indeed, $F_{2+1}=F_3=2$

Inductive step: Say you have $n >2$ stairs. For your first step you can either go one up or two stairs up. By inductive hypothesis, there are $F_{n}$ ways to finish climbing the $n-1$ stairs after having taken a step of $1$ stairs, and there are $F_{n-1}$ ways to finish climbing the $n-2$ stairs after having taken a step of $2$ stairs. So, there are $F_{n}+F_{n-1}=F_{n+1}$ ways to climb $n$ stairs.

OK, so now that we have made a connection between the Fibonacci numbers and the number of ways to climb stairs in this way, we can prove your desired result very quickly:

Let's climb $2n$ stairs. We now know we can do this in $F_{2n+1}$ ways. But note that there are two different possibilities for us climbing those $2n$ stairs: The first way is that we climb the stairs and that at some point we will have climbed exactly $n$ stairs. If this happens, then there are $F_{n+1}$ ways to climb the first $n$ stairs, and also $F_{n+1}$ ways to climb the other $n$ stairs. The second way is that at some point we will have climbed exactly $n-1$ stairs, which can be done in $F_{n}$ ways, after which we take a step of $2$ stairs, and then finish climbing the remaining $n-1$ stairs, which can be done in $F_{n}$ ways. So, it must be true that:

$$F_{2n+1} = F_{n+1} \cdot F_{n+1} + F_{n} \cdot F_{n}$$

Answer 2

My favorite Fibonacci technique is the matrix formulation, which is well worth knowing and easily proved: $$ A^n= \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$ Therefore, $$ \begin{pmatrix}F_{2n+1}&F_{2n}\\F_{2n}&F_{2n-1}\end{pmatrix} =A^{2n} =(A^n)^2 =\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}^2 =\begin{pmatrix}F_n^2+F_{n+1}^2&*\\*&*\end{pmatrix} $$ The omitted terms give other identities, such as $F_{2n} = (F_{n-1}+F_{n+1})F_n$.