EGMO

Una permutación de los enteros $1, 2, \dots , m$ se llama fresca si no existe ningún entero positivo $k \lt m$ tal que los primeros $k$ elementos de la permutación son los números $1, 2, \dots , k$ en algún orden. Sea $f_m$ el número de permutaciones frescas de los enteros $1, 2, \dots , m.$ Muestra que \[f_n \ge n \cdot f_{n-1}\] para todo $n \ge 3$. Por ejemplo, para $m = 4$ la permutación $(3, 1, 4, 2)$ es fresca, mientras que la permutación $(2, 3, 1, 4)$ no lo es.