Show why the equation $F_{2n}=F_{n}^{2}+F_{n-1}^{2}$ is correct by taking an example from the staircase problem

Question

Let's define the Fibonacci numbers by the sequence $F_{0}=0$, $F_{1}=1$, $F_{2}=1$, and $F_{n}$ = $F_{n-1}$ + $F_{n-2}$. Suppose we take a staircase of $n$ stairs, break it in half, and show that $F_{2n}=F_{n}^{2}+F_{n-1}^{2}$. I don't have any clue to get start, anyone help me with this question.

Answer 1

The staircase problem is explained here: How many distinct ways to climb stairs in 1 or 2 steps at a time? where they show that the number of ways to climb $n$ stairs taking only $1$ or $2$ steps is $F_{n+1}$.

The identity to be proven should be $$F_{2n+1}=F_{n+1}^{2}+F_{n}^{2}$$ (note that $3=F_{4}\not=F_{2}^{2}+F_{1}^{2}=1+1$).

Hint. Climbing a staircase with $2n$ steps, we have two cases:

1) we arrive at step $n$ (step $n$ is not broken).

2) we don't arrive at step $n$ (it is broken!) which implies that we arrive at step $n-1$ and then we climb 2 steps.

Answer 2

It is simple to show that $$ F_nF_k+F_{n-1}F_{k-1}=F_{n+k-1}\tag1 $$ holds for $k=1$ and $k=2$. Suppose that $(1)$ holds for $k-1$ and $k-2$, then $$ \begin{align} F_nF_k+F_{n-1}F_{k-1} &=F_n(\color{#C00}{F_{k-1}}+\color{#090}{F_{k-2}})+F_{n-1}(\color{#C00}{F_{k-2}}+\color{#090}{F_{k-3}})\\ &=\color{#C00}{F_{n+k-2}}+\color{#090}{F_{n+k-3}}\\ &=F_{n+k-1}\tag2 \end{align} $$ Thus, $(1)$ holds for all $k\ge1$.

Setting $n=k$ in $(2)$, we get $$ F_n^2+F_{n-1}^2=F_{2n-1}\tag3 $$

Answer 3

We also have the following combinatorial interpretation: $F_{n+2}$ is the number of ways for picking some non-adjacent books from a shelf with $n$ books on it. Let us assume to have $2n-2$ books on a shelf: the number of ways for selecting a subset of non-adjacent books is $F_{2n}$. We either pick the $(n-1)$-th book from the left or we don't: in the former case we are selecting a set of non-adjacent books from a shelf with $n-3$ books on it, then from a shelf with $n-2 $ books on it; in the latter case we are selecting a set of non-adjacent books from a shelf with $n-2$ books, then from a shelf with $n-1$ books. It follows that $$ F_{2n} = F_{n-1} F_n + F_n F_{n+1} = F_n (F_{n-1}+F_{n+1}) = F_nL_n$$ where $L_n$ is the $n$-th Lucas number.