verse permutatie

Een permutatie van de gehele getallen $1, 2, \ldots, m$ wordt vers genoemd als er geen positief geheel getal $k < m$ bestaat waarvoor de eerste $k$ getallen in de permutatie $1, 2, \ldots, k$ in een bepaalde volgorde voorkomen. Laat $f_m$ het aantal verse permutaties zijn van de gehele getallen $1, 2, \ldots, m$.

Bewijs dat $f_n \ge n \cdot f_{n - 1}$ voor alle $n \ge 3$.

Bijvoorbeeld, als $m = 4$, dan is de permutatie $(3, 1, 4, 2)$ vers, terwijl de permutatie $(2, 3, 1, 4)$ dat niet is.