Problem: A permutation of the integers $1, 2, \dots, m$ is called \emph{fresh} if there exists
no positive integer $k < m$ such that the first $k$ numbers
in the permutation are $1, 2, \dots, k$ in some order.
Let $f_m$ be the number of fresh permutations of the integers $1, 2, \dots, m$.
Prove that $f_n \ge n \cdot f_{n - 1}$ for all $n \ge 3$.

Solution: For every fresh permutation on $(1, 2, \dots, n-1)$
we generate $n$ fresh permutations on $(1, 2, \dots, n)$ in the following way:
\begin{itemize}
  \ii Insert $n$ in the $k$th position for $k=1, 2, \dots, n-1$;
  \ii Replace $n-1$ with $n$ and append $n-1$ to the end.
\end{itemize}
For example, $3142$ would generate $53142$, $35142$, $31542$, $31452$ and $31524$.

All permutations generated this way are distinct.
Indeed, the only thing to note is that the second type of permutation
yields a non-fresh permutation when $n$ is deleted
(because $n-1$ is at the end, and $n \ge 3$).
This implies the result.