XLI OM - I - Zadanie 7

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

\[<br />
\binom{2n}{n}\cdot \sqrt{3n} < 4^n<br />
\]

Rozwiązanie

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

\[<br />
(1) \qquad \binom{2n}{n} \cdot \sqrt{3n+1} \leq 4^n.<br />
\]

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

\[<br />
(2) \qquad \binom{2n+2}{n+1} \cdot \sqrt{3(n+1)+1} \leq 4^{n+1}.<br />
\]

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

\[<br />
\begin{split}<br />
\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} =\\<br />
& = \frac{2(2n+1)}{n+1} \cdot \binom{2n}{n} \cdot \sqrt{3n+1} \cdot \sqrt{\frac{3n+4}{3n+1}} \leq \\<br />
& \leq \frac{2(2n+1)}{n+1} \cdot 4^n \cdot \sqrt{\frac{3n+4}{3n+1}}.<br />
\end{split}<br />
\]

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

\[<br />
(3) \qquad \frac{2n+1}{n+1} \cdot \sqrt{\frac{3n+4}{3n+1}} \leq 2.<br />
\]

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

\[<br />
(4) \qquad \frac{(2n+1)^2(3n+4)}{(n+1)^2(3n+1)} \leq 4,<br />
\]

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

\[<br />
\begin{split}<br />
& (4n^2+4n+1)(3n+4) \leq 4(n^2 + 2n+1)(3n+1),\\<br />
& 12n^3 + 28n^2 + 19n+4 \leq 12n^3 + 28n^2+20n+4,\\<br />
& 0 \leq n.<br />
\end{split}<br />
\]

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.

Komentarze

Dodaj nową odpowiedź