On appelle $(F_{n})_{n\in \mathbb{N}}$ la suite de Fibonacci qui est définie de la manière suivante :
$$F_{0} = 0 ~~, ~~ F_{1} = 1 ~~ \text{ et }~~ \forall n \in \mathbb{N}, F_{n+2} = F_{n} + F_{n}$$On souhaite démontrer la formule suivante faisant intervenir des coefficients binomiaux :
$$\forall n \in \mathbb{N}, F_{n} = \sum_{k \in \mathbb{Z}} \binom{n-k-1}{k}=\sum_{k = 0}^{\lfloor \frac {n-1} 2 \rfloor} \binom{n-k -1}{k}$$(On a le fait suivant $\forall (n,k) \in \mathbb{Z}^{2}, (n < k) ~ ou ~ (k < 0) \Rightarrow \binom{n}{k}=0$)
$\newline$
Cette égalité se voit visuellement sur le triangle de Pascal en sommant les diagonales ascendantes :

Méthode 1 - Par récurrence double

$\textbf{1)}$ Démontrer cette formule via récurrence double à l’aide de la relation de Pascal
$\newline$

Méthode 2 - Avec la série génératrice de Fibonacci

$\newline$
$\textbf{2.1)}$ Montrer la formule de Binet : $\forall n \in \mathbb{N}, F_{n} = \frac 1 {\sqrt 5} (\varphi^{n} - \bar{\varphi}^{n})$ où $\varphi = \frac{1 + \sqrt{5}}2$ (appelé nombre d’or) et $\bar\varphi = \frac{1-\sqrt 5}{2}$
$\textbf{2.2})$ Montrer pour tout $x \in ] - \frac 1 {\varphi} ; \frac 1 {\varphi}[$ la série $\sum\limits F_{n} x^{n}$ converge et que $\sum_{n=0}^{+\infty}F_{n} x^{n} = \frac{x}{1 - x - x^{2}}$. Cette série est appelée série génératrice de la suite de Fibonacci
$\textbf{2.3)}$ Retrouver le résultat recherché à l’aide du développement en série entière de $x \mapsto \frac 1 {1-x}$

Méthode 3 - Par double comptage

On se demande de combien de manière différente on peut monter un escalier.
On fixe la contrainte suivante : pour monter un escalier, on peut monter soit une marche, soit deux marches à la fois.

Exemple : Pour un escalier à 3 marches, 3 manières différentes de le monter :
-> 1 marche, 1 marche, 1 marche
-> 2 marches, 1 marche
-> 1 marche, 2 marches

$\textbf{3)}$ Démontrer la formule par double comptage à partir de ce problème de combinatoire.