Niestandardowa indukcja

[karolakkkk]

Udowodnij, że \(n^3 \le 3^n\) dla wszystkich \(n \in \nn\)

[panb]

Nietrudno dowieść, że

1. \(3n^2\le n^3\), dla \(n\ge3\)
2. \(3n+1<n^3\) dla \(n\ge2\)

Nierówność a. jest oczywista: \(n^3-3n^2=n^2(n-3)\ge0\) dla \(n\ge 3\)
Nierówność b. trochę trudniej wykazać, ale zauważmy, że ciąg \(a_n=n^3-3n-1\) jest rosnący.
Istotnie, dla \(n\ge2,\quad a_{n+1}-a_n=3n^2+3n-2\ge3n^2-3n-n=3n^2+2n>0\)
Zatem dla \(n\ge2,\quad a_n\ge a_2=1>0 \So n^3>3n+1\)

Sprawdzamy prawdziwość twierdzenia dla n=1 i 2. Oczywiście twierdzenie jest prawdziwe.

Zakładamy, że \(n^3\le 3^n\). Dla \(n\ge3\), mamy
\((n+1)^3= \left( n^3\right) + \left(3n^2 \right) + \left(3n+1 \right) \le n^3+n^3+n^3\le 3^n+3^n+3^n=3 \cdot 3^n=3^{n+1}\)
co kończy dowód indukcyjny.