XLI OM - I - Zadanie 7

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Udowodnić, że dla każdej liczby naturalnej $n$ zachodzi nierówność

$ \binom{2n}{n}\cdot \sqrt{3n} < 4^n $

Rozwiązanie

\spos{I} Udowodnimy nierówność silniejszą (patrz Uwaga 1):

$ (1) \qquad \binom{2n}{n} \cdot \sqrt{3n+1} \leq 4^n. $

Oczywiście nierówność dana w zadaniu wynika z (1) natychmiast.

Dowód będzie indukcyjny. Dla $n = 1$ nierówność (1) zachodzi (w postaci równości).
Przyjmijmy słuszność (1) dla pewnej liczby naturalnej $n$ . Chcemy wykazywać, że

$ (2) \qquad \binom{2n+2}{n+1} \cdot \sqrt{3(n+1)+1} \leq 4^{n+1}. $

Korzystając z założenia indukcyjnego, przekształcamy lewą stronę (2), jak następuje:

$ \begin{split} \binom{2n+2}{n+1} \cdot \sqrt{3n+4} & = \binom{2n}{n} \cdot \frac{(2n+1)(2n+2)}{(n+1)(n+1)} \cdot \sqrt{3n+4} =\\ & = \frac{2(2n+1)}{n+1} \cdot \binom{2n}{n} \cdot \sqrt{3n+1} \cdot \sqrt{\frac{3n+4}{3n+1}} \leq \\ & \leq \frac{2(2n+1)}{n+1} \cdot 4^n \cdot \sqrt{\frac{3n+4}{3n+1}}. \end{split} $

Nierówność (2) będzie udowodniona, gdy pokażemy, że

$ (3) \qquad \frac{2n+1}{n+1} \cdot \sqrt{\frac{3n+4}{3n+1}} \leq 2. $

Podnosząc (3) stronami do kwadratu otrzymujemy nierówność

$ (4) \qquad \frac{(2n+1)^2(3n+4)}{(n+1)^2(3n+1)} \leq 4, $

która jest równoważna (3). Przekształcamy (4) dalej, stosując przejścia równoważne:

$ \begin{split} & (4n^2+4n+1)(3n+4) \leq 4(n^2 + 2n+1)(3n+1),\\ & 12n^3 + 28n^2 + 19n+4 \leq 12n^3 + 28n^2+20n+4,\\ & 0 \leq n. \end{split} $

Ostatnia nierówność jest prawdziwa, a przy tym równoważna nierówności (4) - a więc i (3). To zaś wystarczy do udowodnienia tezy indukcyjnej (2).

Na mocy zasady indukcji nierówność (1) zachodzi dla każdej liczby naturalnej $n$ .

Uwaga 1. Gdybyśmy próbowali przeprowadzić dowód indukcyjny nierówności danej w zadaniu w jej oryginalnej postaci, spotkałoby nas niepowodzenie. Przy dowodzeniu twierdzeń przez indukcję nierzadko zdarza się, że wzmocnienie tezy ułatwia problem, bowiem w kroku indukcyjnym jest moment, gdy teza staje się założeniem. Omawiane zadanie stanowi typowy przykład takiej właśnie sytuacji.