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

Егер $1,2, \ldots, m$ сандарының орын алмастыруында, алдыңғы $k$ сан $1,2, \ldots, k$ сандарының қандай да бiр орын алмастыруы болатындай натурал $k$ < $m$ саны табылмаса, онда ондай орын алмастыруыды жаңа деп атайымыз. $1,2, \ldots, m$ сандарының жаңа орын алмастыруларының санын $f_{m}$ арқылы белгiлейiк. Барлық $n \geqslant 3$ үшiн $f_{n} \geqslant n \cdot f_{n-1}$ теңсiздiгiн дәлелдеңiз. Мысалы, егер $m=4$ болса, онда ($3,1,4,2$) орын алмастыруы жаңа болып саналады, ал ($2,3,1,4$) орын алмастыруы — жаңа емес.