exo7 2918

Quel est le nombre de parties à $p$ éléments de $\{1, \dots, n\}$ ne contenant pas d’éléments consécutifs ?

Soit $t_n$ le nombre de parties de $\{1, \dots, n\}$ de cardinal quelconque sans éléments consécutifs.

Montrer que $t_{n+2} = t_{n+1} + t_n$, $t_{2n+1} = t_n^2 + t_{n-1}^2$, et $t_{2n} = t_n^2 - t_{n-2}^2$.

Calculer $t_{50}$.