szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 27 lut 2017, o 20:00 
Użytkownik

Posty: 10
Lokalizacja: Polska
Dla n>1 udowodnij nierówność:
{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?
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2017, o 20:10 
Użytkownik
Avatar użytkownika

Posty: 6642
n>3

{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
n=2 \Rightarrow  {4 \choose 2}=6>4=2 {2 \choose 1} \\ 
n=3 \Rightarrow  {6 \choose 2}=20>6=2 {3 \choose 1}
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2017, o 20:13 
Użytkownik

Posty: 10
Lokalizacja: Polska
Gdzie się podziało drugie n! z mianownika? :>
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2017, o 20:33 
Użytkownik
Avatar użytkownika

Posty: 13164
Lokalizacja: Wrocław
Zostało uproszczone z (2n)!. Wszakże (2n)!=n! \cdot n(n+1)\cdot (n+2)\cdot \dots 2n
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2017, o 20:43 
Użytkownik

Posty: 10
Lokalizacja: Polska
W jaki sposób (2n)! rozkłada się na "{(2n)!}={n \cdot n! \cdot (n+1)(n+2)...(2n-1)(2n)}? :?
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2017, o 20:47 
Użytkownik
Avatar użytkownika

Posty: 13164
Lokalizacja: Wrocław
Sorry, idiotyczna literówka, powinno być bez jednego z tych n.
(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
{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:
\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 {2n \choose n}=\sum_{k=0}^{n}{n \choose k}^2
 \ge  \frac{1}{n+1}2^{2n}

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

2^{\circ} Zakładamy, że dla pewnego n \in \NN jest
2^{2n} \ge 4n^2. Wówczas
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:
4n \ge 2n+2 podniesionej do kwadratu.
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2017, o 20:59 
Użytkownik

Posty: 10
Lokalizacja: Polska
Nie do końca wiem jak udowodnić ten fragment: {2n \choose n}= \sum_{k=0}^{n}{n \choose k}^2 :(
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2017, o 21:12 
Użytkownik
Avatar użytkownika

Posty: 13164
Lokalizacja: Wrocław
Wspomniałem o interpretacji kombinatorycznej.

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

Mamy zaś {n \choose k}={n \choose n-k} - można to udowodnić, rozpisując na silnie z definicji symbolu Newtona i skracając. Zatem
{n \choose k}^2={n \choose k}\cdot {n \choose n-k}, czyli
\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 {2n \choose n} po lewej stronie). Powiedzmy, że rybak złowił 2n szczupaków, przy czym powrzucał je do dwóch balii, po n ryb w każdej. Spośród złowionych ryb zamierza sprzedać n, zaś pozostałych n sobie zjeść. Z jednej strony jest jasnym, że może wybrać ryby do zjedzenia na {2n \choose n} sposobów (wszystkich ryb jest 2n, wybiera n).
Z drugiej strony rybak może wziąć k ryb z jednej balii dla k=0,1,\dots n i n-k ryb z drugiej balii do sprzedaży, by w sumie wybrać n. Czyli z reguły mnożenia wynika, że wszystkich wyborów n ryb na sprzedaż jest
{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 {2n \choose n}= \sum_{k=0}^{n} {n \choose k}^2
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2017, o 21:22 
Użytkownik

Posty: 15820
Lokalizacja: Bydgoszcz
A może zauważyć,że
\binom{2n}{1}<\binom{2n}{2}<\binom{2n}{3}<\dots<\binom{2n}{n}

oraz że 2\binom{n}{1}=\binom{2n}{1}
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2017, o 21:41 
Użytkownik

Posty: 10
Lokalizacja: Polska
Dziękuje wszystkim za pomoc już wszystko rozumiem :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Dowód nierówności  Sebastian R.  2
 dowód nierownosci  Uzo  4
 Dowód nierówności - zadanie 2  agorniak  0
 Dowód nierówności - zadanie 3  agorniak  0
 Dowód nierówności - zadanie 4  kawafis44  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl