Avrupa Kızlar Matematik Olimpiyatı 2020 Soru 4

[matematikolimpiyati]

$1,2,...,m$ tam sayılarının bir permütasyonunda$,$ ilk $k$ sayı $1,2,...,k$'nin bir sıralanışı olacak şekilde $k<m$ pozitif tam sayısı bulunmuyorsa$,$ bu permütasyona $\textit{taze}$ denir. $1,2,...,m$ tam sayılarının taze permütasyonlarının sayısı $f_m$ olsun.

Her $n \geq 3$ için $f_n \geq n \cdot f_{n-1}$ olduğunu gösteriniz.

Örneğin $m=4$ için$,$ $(3,1,4,2)$ permütasyonu taze iken $(2,3,1,4)$ permütasyonu taze değildir.