Европейская математическая олимпиада среди девочек (EGMO). 2020 год. Нидерланды

Перестановку целых чисел $1,2, \ldots, m$ будем называть свежей, если не существует положительного целого $k < m$ такого, что первые $k$ чисел в этой перестановке — это $1,2, \ldots, k$ в некотором порядке. Пусть $f_{m}$ — количество всех свежих перестановок чисел $1,2, \ldots, m$.
   Докажите, что $f_{n} \geqslant n \cdot f_{n-1}$ для всех $n \geqslant 3$.
   Например, если $m=4$, то перестановка ($3,1,4,2$) является свежей, а перестановка ($2,3,1,4$) не является.