Interesting identities/formulae/results involving Fibonacci numbers.

Question

Recently I presented the topic Fibonacci numbers in my class. It was massively successful and it has motivated me to conduct the part $2$ of the presentation. But unfortunately I have not sufficient data to proceed. I shall be thankful if you guys can present here some interesting or so called mind blowing identities including Fibonacci numbers.

I used following identities in the previous presentation:

$1.$ As observed by Johannas Kepler, $\frac{F_{n+1}}{F_n}\to \phi$ as $n\to\infty$.

$2.$ Binet's formula: $F_n=\frac{\phi^n-(\phi^{-n})}{\sqrt{5}}=\frac{\phi^n-(\phi^{-n})}{2\phi-1}$.

$3.$ $\phi^n=F_n\phi+F_{n-1}$

$4.$ Number of binary strings of length $n$ without consecutive $1's$ is the Fibonacci number $F_{n+2}$. For instance if $n=2${length of string} then there are total $2^2=4$ strings $00,01,10,11$. Note that $\underbrace{00,01,10}_{3 \text{times 1 is not being repeated}}$ and $3=F_4$.

$5.$ Number of ordered ways of writing a number $n$ in terms of sum of $1's$ and $2's$ is $F_{n+1}$. For instance $2=2=1+1\to $ two ways $=F_3$ ways.

$6.$ Pascal triangle and Fibonacci numbers:

This image is quite self explainatory, the Fibonacci numbers are sum of shallow diagonals of Pascal triangle. We represent it mathematically as $F_n={\sum_{k=0}^{[\frac{n}{2}]}}$ ${n-k+1}\choose{k}$ where $[ \ ]$ is floor function.

Side note: Whatever result you are providing, please link the source and try to give the proof if it can be understood by general audience (does not require much knowledge).

Almost all of the content I have given is available on Wikipedia.

Thanks.

Update: Thanks to @Claude, this gives a lot of instances where Fibonacci numbers are seen.

Update: As the answers are not of the form I expected(though answer by Frpzzd has good content), so let me show you a masterpiece. This is something which we can call interesting

Answer 1

Here are a few ideas.

1.Talk about the relationship between the Fibonacci numbers and the Lucas numbers. The Lucas numbers are defined recursively in the same way as the Fibonacci numbers, but it starts with $2$ and $1$ instead of $1$ and $1$. There exist a few interesting relationships between the two sequences, such as $$F_{2n}=L_nF_n$$

2. The Fibonacci numbers have some interesting properties related to divisibility such as:

   • for each positive integer, $k$, the Fibonacci number $F_n$ evenly divides the Fibonacci number $F_{kn}$.
   • $GCD(F_n,F_m)=F_{GCD(n,m)}$.
   • The function $M(x)=F_x \bmod m$ is periodic for any given $m$.

3. Talk about the extension of $F_n$ to negative $n$. These are given by the formula $$F_{-n}=(-1)^{n+1}F_n$$

4. Prove that the number of ways to cover a $2$ by $n$ checkerboard with $2$ by $1$ dominoes is $F_{n+1}$.

Answer 2

The error when approximating the golden ratio from above as a ratio of consecutive Fibonacci numbers is an Egyptian fraction of Fibonacci numbers.

$$\frac{F(2n+1)}{F(2n)}-\varphi = \sum_{k=0}^\infty \frac{1}{F(n2^{k+2})}$$

https://math.stackexchange.com/a/2307929/134791