XI OM - III - Zadanie 1

Zawody matematyczne:

XI OM, 1959-1960

Etap:

III

Udowodnić, że jeżeli $n$ jest liczbą całkowitą większą od $4$ , to $2^n$ jest większe, od $n^2$ .

Rozwiązanie

Ponieważ $2^5 > 5^2$ , więc nierówność $2^n > n^2$ jest prawdziwa dla $n = 5$ . Przypuśćmy, że ta nierówność jest prawdziwa, gdy $n$ równa się pewnej liczbie całkowitej $k > 4$ , tj. że $^k > k^2$ . Wówczas

$ 2^{k +1} = 2^k \cdot 2 > k^2 \cdot 2 = k^2 + k^2 > k^2 + 2k + 1 = (k + 1)^2. $

Nierówność $2^n > n^2$ jest więc prawdziwa, gdy $n = k + 1$ . Na mocy indukcji zupełnej nierówność ta jest prawdziwa dla każdego całkowitego $n > 4$ .

W powyższym dowodzie oparliśmy się na tym, że gdy $k > 4$ , to $k^2 > 2k + 1$ . Istotnie, nierówność $k^2 > 2k + 1$ jest równoważna nierówności $k (k - 2) > 1$ , która jest prawdziwa dla $k > 4$ , a nawet dla $k \geq 3$ .

Uwaga. Prawdziwe jest twierdzenie ogólniejsze: jeżeli $a$ jest liczbą całkowitą większą od $1$ , a $n$ - liczbą całkowitą większą od $a^2$ , to

$ (1) \qquad a^n > n^a. $

Dla $a = 2$ dowód już przeprowadziliśmy wyżej, przyjmiemy więc że $a > 2$ i zastosujemy indukcję zupełną. Nierówność (1) jest prawdziwa, gdy $n = a^2$ ; istotnie $a^{a^2}$ jest przy $a > 2$ większe niż $(a^2)^a = a^{2n}$ , gdyż z nierówności $a > 2$ wynika, że $a^2 > 2a$ .

Przypuśćmy, że dla pewnego całkowitego $k \geq a^2$ jest

$ a^k > k^a; $

mamy dowieść, że

$ a^{k+1} > (k + 1)^a. $

Według założenia indukcyjnego $a^{k+1} = a^k \cdot a > k^a \cdot a$ , więc wystarczy dowieść, że gdy $a > 2$ i $k \geq a^2$ , to $k^a \cdot a > (k + 1)^a$ , czyli że

$ \left( \frac{k}{k+1} \right)^a \cdot a > 1. $

W rzeczy samej, gdy $a > 2$ i $k \geq a^2$ , to

$ \begin{split} \left( \frac{k}{k+1} \right)^a \cdot a &= \left( 1 - \frac{1}{k+1} \right)^a \cdot a > \left( 1 - \frac{a}{k+1} \right) a = \\ &=a - \frac{a^2}{k+1} \geq a - \frac{a^2}{a^2+1} > a-1 > 1, \end{split} $

czego należało dowieść. (W dowodzie oparliśmy się na twierdzeniu, że gdy $n$ jest liczbą całkowitą większą od $1$ , a $d > -1$ , to $(1 + d)^n > 1 + nd$ . Dowód tej nierówności łatwo uzyskać metodą indukcji. Patrz Zadania z Olimpiad Matematycznych, tom II, zadanie 36).