EGMO 2020 Problem 4

A permutation of the integers $1, 2, \ldots, m$ is called fresh if there exists no positive integer $k < m$ such that the first $k$ numbers in the permutation are $1, 2, \ldots, k$ in some order. Let $f_m$ be the number of fresh permutations of the integers $1, 2, \ldots, m$ .

Prove that $f_n \ge n \cdot f_{n - 1}$ for all $n \ge 3$ .

For example, if $m = 4$ , then the permutation $(3, 1, 4, 2)$ is fresh, whereas the permutation $(2, 3, 1, 4)$ is not.