3. Zadatak

Koristeći princip matematičke indukcije dokazat ćemo da vrijedi $a_n\geq\sqrt{n!}$ za svaki prirodni broj $n$.

Baza indukcije je očito zadovoljena jer za $n=1$ i $n=2$ imamo $a_1=1\geq\sqrt{1!}$ i $a_2=2\geq\sqrt2=\sqrt{2!}$.

Pretpostavimo da vrijedi za $n-2$ i $n-1$, odnosno da vrijedi $a_{n-2}\geq\sqrt{(n-2)!}$ i $a_{n-1}\geq\sqrt{(n-1)!}$.

Tada je

$$a_n=a_{n-1}+(n-1)a_{n-2} \geq\sqrt{(n-1)!}+(n-1)\sqrt{(n-2)!} =\sqrt{(n-1)!}(1+\sqrt{n-1}).$$

Kako je $(1+\sqrt{n-1})^2=1+2\sqrt{n-1}+n-1>n$, slijedi da je $1+\sqrt{n-1}>\sqrt n$.

Zato je

$$a_n\geq\sqrt{(n-1)!}(1+\sqrt{n-1}) >\sqrt{(n-1)!}\cdot\sqrt n =\sqrt{n!},$$

čime je dokazan korak indukcije, a samim time i tvrdnja zadatka.