3. Zadatak

Prvo rješenje.

Tvrdnju ćemo dokazati matematičkom indukcijom.

Baza $n=1$ očito vrijedi jer je $a_1=1$.

Pretpostavimo da tvrdnja vrijedi za neki prirodni broj $n$.

Ako je $0<a_{n+1}<\frac1{n+1}$, tada je

$$a_n=a_{n+1}^2+a_{n+1} <\frac1{(n+1)^2}+\frac1{n+1} =\frac{n+2}{(n+1)^2}.$$

Također, vrijedi $\frac{n+2}{(n+1)^2}<\frac1n$ jer je $(n+1)^2=n(n+2)+1>n(n+2)$.

Dobili smo kontradikciju, pa mora vrijediti $a_{n+1}\geq\frac1{n+1}$, čime je korak indukcije dokazan.

Drugo rješenje.

Tvrdnju ćemo dokazati matematičkom indukcijom.

Baza $n=1$ očito vrijedi jer je $a_1=1$.

Pretpostavimo da tvrdnja vrijedi za neki prirodni broj $n$.

Vrijedi da je

$$a_{n+1}=\frac{-1\pm\sqrt{1+4a_n}}{2}.$$

Kako su svi članovi niza pozitivni, mora vrijediti

$$a_{n+1}=\frac{-1+\sqrt{1+4a_n}}{2}.$$

Kako je $a_n\geq\frac1n$ po pretpostavci indukcije, dobivamo da je

$$a_{n+1}\geq\frac{\sqrt{1+\frac4n}-1}{2}.$$

Pokažimo da je

$$\frac{\sqrt{1+\frac4n}-1}{2}\geq\frac1{n+1}.$$

Ta nejednakost je, nakon sređivanja i kvadriranja, ekvivalentna s tvrdnjom

$$1+\frac4n\geq\left(1+\frac2{n+1}\right)^2.$$

Ta tvrdnja vrijedi jer je

$$\left(1+\frac2{n+1}\right)^2 =1+\frac4{n+1}+\frac4{(n+1)^2} =1+\frac{4(n+2)}{(n+1)^2} <1+\frac4n.$$

Sada vidimo da je

$$a_{n+1}\geq\frac{\sqrt{1+\frac4n}-1}{2}\geq\frac1{n+1},$$

čime je dokazan korak indukcije.