Q4 Matemática  (EGMO 2020)

Uma permutação dos inteiros $1,2,\dots ,m$ é chamada de nova se não existir nenhum inteiro positivo $k<m$ tal que os primeiros $k$ números na permutação sejam $1,2,\dots ,k$ in alguma ordem. Seja $f_m$ o número de novas permutações dos inteiros $1,2,\dots ,m$. Prove que $f_n\ge n\cdot f_{n-1}$ para todo $n\ge 3$. Por exemplo, se $m=4$, então a permutação $(3,1,4,2)$ é nova, enquanto a permutação $(2,3,1,4)$ não é.