Exercice 33

Notons $T_{n} = \sum_{k=0}^{n} \binom{n-k}{k}$ ; grâce à la convention $\binom{a}{b} = 0$ pour $b > a$, on peut sommer sur tous les $k \geqslant 0$. Alors $T_{0} = 1 = F_{1}$, $T_{1} = 1 = F_{2}$, et par la formule de Pascal, $$T_{n+2} = \sum_{k \geqslant 0} \binom{n+1-k}{k} + \sum_{k \geqslant 1} \binom{n+1-k}{k-1} = T_{n+1} + \sum_{j \geqslant 0} \binom{n-j}{j} = T_{n+1} + T_{n}.$$ Les suites $(T_{n})$ et $(F_{n+1})$ vérifient la même relation de récurrence et ont les mêmes deux premiers termes : par récurrence double, elles sont égales. $$\boxed{\sum_{k=0}^{n} \binom{n-k}{k} = F_{n+1}}$$ Sur le triangle de Pascal, $T_{n}$ est la somme des coefficients d'une « diagonale montante » : on part du bord gauche de la ligne $n$ et l'on remonte d'une ligne en avançant d'un rang. Les sommes de ces diagonales sont $1, 1, 2, 3, 5, 8, \dots$