Dowód nierówności

[MrSqoobany]

Dla \(\displaystyle{ n>1}\) udowodnij nierówność:
\(\displaystyle{ {2n\choose n} > 2 \cdot {n \choose 1} \\
\frac{(2n)!}{n!(2n-n)!} > \frac{2 \cdot (n!)}{(n-1)!} \\
\frac{(2n)!}{n!n!} > \frac{2n!}{(n-1)!} \\
\frac{(2n)!}{n!n!} > \frac{2n(n-1)!}{(n-1)!} \\
\frac{(2n)!}{n!n!} > 2n}\)
Tutaj się zatrzymałem i nie wiem co dalej, czy robię gdzieś błąd?

[kerajs]

\(\displaystyle{ n>3}\)

\(\displaystyle{ {2n \choose n}= \frac{(2n)!}{n!n!}= \frac{(n+1)(n+2)...(2n-1)(2n)}{n!}= \frac{2n \cdot (n+1)(n+2)...(2n-1)}{1 \cdot 2 \cdot 3 \cdot ... \cdot n}=\\= 2n \cdot \frac{n+1}{2} \cdot \frac{n+2}{3} \cdot... \cdot \frac{2n-1}{n} \ge 2n \cdot 1 \cdot 1 \cdot ... \cdot 1=2n= 2 \cdot {n \choose 1}}\)

Edit
\(\displaystyle{ n=2 \Rightarrow {4 \choose 2}=6>4=2 {2 \choose 1} \\
n=3 \Rightarrow {6 \choose 2}=20>6=2 {3 \choose 1}}\)

[MrSqoobany]

Gdzie się podziało drugie \(\displaystyle{ n!}\) z mianownika? :>

[Premislav]

Zostało uproszczone z \(\displaystyle{ (2n)!}\). Wszakże \(\displaystyle{ (2n)!=n! \cdot n(n+1)\cdot (n+2)\cdot \dots 2n}\)

[MrSqoobany]

W jaki sposób \(\displaystyle{ (2n)!}\) rozkłada się na "\(\displaystyle{ {(2n)!}={n \cdot n! \cdot (n+1)(n+2)...(2n-1)(2n)}}\)?

[Premislav]

Sorry, idiotyczna literówka, powinno być bez jednego z tych \(\displaystyle{ n}\).
\(\displaystyle{ (2n)!=n! \cdot(n+1) \cdot(n+2)\dots \cdot 2n}\)
Wynika to wprost z definicji silni.

Przy okazji zaproponuję nieco inne rozwiązanie. Łatwo udowodnić, że
\(\displaystyle{ {2n \choose n}= \sum_{k=0}^{n}{n \choose k}^2}\)
(wskazówka: interpretacja kombinatoryczna).


a więc z nierówności Cauchy'ego-Schwarza mamy:
\(\displaystyle{ \left( \sum_{k=0}^{n}1^2 \right)\left( \sum_{k=0}^{n}{n \choose k}^2 \right) \ge \left( \sum_{k=0}^{n}{n \choose k}\right)^2=2^{2n}}\)

Czyli \(\displaystyle{ {2n \choose n}=\sum_{k=0}^{n}{n \choose k}^2
\ge \frac{1}{n+1}2^{2n}}\)

Wystarczy więc wykazać, że
\(\displaystyle{ \frac{1}{n+1}2^{2n}>2{n \choose 1}=2n}\) dla \(\displaystyle{ n>1}\), a to z kolei wzmacniamy do
\(\displaystyle{ 2^{2n} \ge 4n^2}\),
a to łatwo wykazujemy indukcyjnie:
\(\displaystyle{ 1^{\circ}}\) dla \(\displaystyle{ n=1}\) mamy \(\displaystyle{ L=4 \ge 4=P}\);

\(\displaystyle{ 2^{\circ}}\) Zakładamy, że dla pewnego \(\displaystyle{ n \in \NN}\) jest
\(\displaystyle{ 2^{2n} \ge 4n^2}\). Wówczas
\(\displaystyle{ 2^{2(n+1)}=4 \cdot 2^{2n}\ge 4 \cdot 4n^2=16n^2 \ge 4(n+1)^2}\)
przy czym ostatnia nierówność wynika z:
\(\displaystyle{ 4n \ge 2n+2}\) podniesionej do kwadratu.

[MrSqoobany]

Nie do końca wiem jak udowodnić ten fragment: \(\displaystyle{ {2n \choose n}= \sum_{k=0}^{n}{n \choose k}^2}\)

[Premislav]

Wspomniałem o interpretacji kombinatorycznej.

\(\displaystyle{ {2n \choose n}}\) to liczba n-elementowych podzbiorów zbioru o \(\displaystyle{ 2n}\) elementach.

Mamy zaś \(\displaystyle{ {n \choose k}={n \choose n-k}}\) - można to udowodnić, rozpisując na silnie z definicji symbolu Newtona i skracając. Zatem
\(\displaystyle{ {n \choose k}^2={n \choose k}\cdot {n \choose n-k}}\), czyli
\(\displaystyle{ \sum_{k=0}^{n}{n \choose k}^2= \sum_{k=0}^{n}{n \choose k}\cdot {n \choose n-k}}\)

To teraz popatrzmy, jaką interpretację możemy nadać tej sumie (i okaże się, że taką samą, jak symbolowi \(\displaystyle{ {2n \choose n}}\) po lewej stronie). Powiedzmy, że rybak złowił \(\displaystyle{ 2n}\) szczupaków, przy czym powrzucał je do dwóch balii, po \(\displaystyle{ n}\) ryb w każdej. Spośród złowionych ryb zamierza sprzedać \(\displaystyle{ n}\), zaś pozostałych \(\displaystyle{ n}\) sobie zjeść. Z jednej strony jest jasnym, że może wybrać ryby do zjedzenia na \(\displaystyle{ {2n \choose n}}\) sposobów (wszystkich ryb jest 2n, wybiera n).
Z drugiej strony rybak może wziąć \(\displaystyle{ k}\) ryb z jednej balii dla \(\displaystyle{ k=0,1,\dots n}\) i \(\displaystyle{ n-k}\) ryb z drugiej balii do sprzedaży, by w sumie wybrać \(\displaystyle{ n}\). Czyli z reguły mnożenia wynika, że wszystkich wyborów n ryb na sprzedaż jest
\(\displaystyle{ {n \choose 0}\cdot {n \choose n-0}+{n \choose 1} \cdot {n \choose n-1}+\dots+{n \choose n}\cdot {n \choose n-n}=\\= \sum_{k=0}^{n}{n \choose k}{n \choose n-k}= \sum_{k=0}^{n} {n \choose k}^2}\)

Stąd \(\displaystyle{ {2n \choose n}= \sum_{k=0}^{n} {n \choose k}^2}\)

[a4karo]

A może zauważyć,że
\(\displaystyle{ \binom{2n}{1}<\binom{2n}{2}<\binom{2n}{3}<\dots<\binom{2n}{n}}\)

oraz że \(\displaystyle{ 2\binom{n}{1}=\binom{2n}{1}}\)

[MrSqoobany]

Dziękuje wszystkim za pomoc już wszystko rozumiem