Strona 1 z 3
Szacowanie dwumianu Newtona
: 13 kwie 2008, o 14:32
autor: tece
Udowodnij, że \(\displaystyle{ {n\choose s} \leqslant \left( \frac{ne}{s} \right) ^{s}}\) dla wszystkich \(\displaystyle{ n \in \NN}\) oraz \(\displaystyle{ s \in \lbrace 0 \rbrace \cup \NN}\).
Szacowanie dwumianu Newtona
: 7 kwie 2010, o 18:21
autor: paluch102
Witam
Ponawiam prośbę o jasne wytłumaczenie tego zadanka.
Szacowanie dwumianu Newtona
: 17 maja 2018, o 21:33
autor: popiszsieplay
Również ponawiam prośbę o rozwiązanie zadania
Szacowanie dwumianu Newtona
: 17 maja 2018, o 22:27
autor: Janusz Tracz
Ja to widzę tak, że można by to zrobić indukcją po \(\displaystyle{ s \le n}\). No i nierówność nie ma sensu dla \(\displaystyle{ s=0}\) jak piszą w zadaniu. Więc zakładam, że \(\displaystyle{ s,n\in\NN}\) i \(\displaystyle{ s \le n}\). Dla \(\displaystyle{ s=1}\) nierówność jest oczywista. Zakładamy więc, że nierówność jest prawdziwa dla jakiegoś \(\displaystyle{ s}\) i sprawdzamy czy takie założenie implikuje:
\(\displaystyle{ \frac{n!}{(s+1)!(n-s+1)!} \le \left( \frac{en}{s+1} \right)^{s+1}}\)
\(\displaystyle{ \frac{n!}{s!(n-s)!} \le \left( \frac{en}{s+1} \right)^{s+1}(s+1)(n-s+1)}\)
Więc jeśli spełniona będzie nierówność:
\(\displaystyle{ \left( \frac{en}{s} \right)^{s} \le \left( \frac{en}{s+1} \right)^{s+1}(s+1)(n-s+1)}\)
To teza \(\displaystyle{ T(s+1)}\) też będzie spełniona ze względy na założenie \(\displaystyle{ T(s)}\).
Nierówność ta przekształca się do:
\(\displaystyle{ \left( \frac{s+1}{s} \right)^{s} \le en(n-s+1)}\)
Zauważy, że wyrażanie po lewej stronie jest malejące ze względy na \(\displaystyle{ s}\), więc wystarczy sprawdzić tylko graniczny przypadek \(\displaystyle{ s=n}\) (po prawej) co daje:
\(\displaystyle{ \left( \frac{s+1}{s} \right)^{s} \le e}\)
Nierówność ta jest już znana i wynika z nierówności Bernoulliego. Tym samym kończąc dowód.
Re: Szacowanie dwumianu Newtona
: 17 maja 2018, o 23:24
autor: Premislav
Można również zapisać, że
dla \(\displaystyle{ n\ge s}\) jest \(\displaystyle{ {n \choose s}=\frac{1}{s!} \prod_{k=1}^{s}(n-k+1)}\), przekształcić tezę do równoważnej, z uwagi na powyższe, postaci
\(\displaystyle{ \prod_{k=1}^{s}(n-k+1) \le s!\left( \frac{ne}{s}\right)^s}\)
i użyć szacowania
\(\displaystyle{ s!\ge \left( \frac s e\right)^s}\) (jego dowód to zwykle też indukcja),
a wówczas wystarczy udowodnić, że
\(\displaystyle{ \prod_{k=1}^{s}(n-k+1)\le n^s}\),
co jest oczywiste, gdyż zarówno po lewej, jak i po prawej stronie mamy po \(\displaystyle{ s}\) dodatnich czynników (tylko z prawej wszystkie są równe \(\displaystyle{ n}\)) i każdy czynnik z lewej strony jest nie większy niż \(\displaystyle{ n}\).
Re: Szacowanie dwumianu Newtona
: 18 maja 2018, o 08:17
autor: Janusz Tracz
Fajne ale złotego szpadla Ci nie oddam!
Re: Szacowanie dwumianu Newtona
: 19 maja 2018, o 00:06
autor: popiszsieplay
Dziękuję, chłopaki!
Szacowanie dwumianu Newtona
: 30 kwie 2019, o 09:57
autor: Wysu
Janusz Tracz pisze:Ja to widzę tak, że można by to zrobić indukcją po \(\displaystyle{ s \le n}\). No i nierówność nie ma sensu dla \(\displaystyle{ s=0}\) jak piszą w zadaniu. Więc zakładam, że \(\displaystyle{ s,n\in\NN}\) i \(\displaystyle{ s \le n}\). Dla \(\displaystyle{ s=1}\) nierówność jest oczywista. Zakładamy więc, że nierówność jest prawdziwa dla jakiegoś \(\displaystyle{ s}\) i sprawdzamy czy takie założenie implikuje:
\(\displaystyle{ \frac{n!}{(s+1)!(n-s+1)!} \le \left( \frac{en}{s+1} \right)^{s+1}}\)
\(\displaystyle{ \frac{n!}{s!(n-s)!} \le \left( \frac{en}{s+1} \right)^{s+1}(s+1)(n-s+1)}\)
Więc jeśli spełniona będzie nierówność:
\(\displaystyle{ \left( \frac{en}{s} \right)^{s} \le \left( \frac{en}{s+1} \right)^{s+1}(s+1)(n-s+1)}\)
To teza \(\displaystyle{ T(s+1)}\) też będzie spełniona ze względy na założenie \(\displaystyle{ T(s)}\).
Nierówność ta przekształca się do:
\(\displaystyle{ \left( \frac{s+1}{s} \right)^{s} \le en(n-s+1)}\)
Zauważy, że wyrażanie po lewej stronie jest malejące ze względy na \(\displaystyle{ s}\), więc wystarczy sprawdzić tylko graniczny przypadek \(\displaystyle{ s=n}\) (po prawej) co daje:
\(\displaystyle{ \left( \frac{s+1}{s} \right)^{s} \le e}\)
Nierówność ta jest już znana i wynika z nierówności Bernoulliego. Tym samym kończąc dowód.
Podstawiając
\(\displaystyle{ n}\) za
\(\displaystyle{ s}\) otrzymujemy po prawej stronie
\(\displaystyle{ en}\). Chciałbym zapytać w jaki sposób to
\(\displaystyle{ n}\) się tam skróciło.
Z góry dziękuję za odpowiedź.
Re: Szacowanie dwumianu Newtona
: 30 kwie 2019, o 10:03
autor: Janusz Tracz
Nie skróciło się. Liczba \(\displaystyle{ n}\) jest naturalna zatem \(\displaystyle{ e \le en}\) a stąd już mamy
\(\displaystyle{ \left( \frac{s+1}{s} \right)^{s} \le e \le en}\)
Szacowanie dwumianu Newtona
: 9 maja 2019, o 16:29
autor: Wysu
Mam jeszcze jedno pytanie - mianowicie, czy możemy korzystać przy tym dowodzie z indukcji matematycznej jeśli \(\displaystyle{ s}\) jest ograniczone przez \(\displaystyle{ n}\)?
Próbowałem również dowodzić za pomocą indukcji ale nie po \(\displaystyle{ s}\) tylko po \(\displaystyle{ n}\) i szczerze mówiąc nie za bardzo wtedy wychodzi...
Re: Szacowanie dwumianu Newtona
: 22 maja 2023, o 00:05
autor: kaminie318
Janusz Tracz pisze: ↑17 maja 2018, o 22:27
Ja to widzę tak, że można by to zrobić indukcją po
\(\displaystyle{ s \le n}\). No i nierówność nie ma sensu dla
\(\displaystyle{ s=0}\) jak piszą w zadaniu. Więc zakładam, że
\(\displaystyle{ s,n\in\NN}\) i
\(\displaystyle{ s \le n}\). Dla
\(\displaystyle{ s=1}\) nierówność jest oczywista. Zakładamy więc, że nierówność jest prawdziwa dla jakiegoś
\(\displaystyle{ s}\) i sprawdzamy czy takie założenie implikuje:
\(\displaystyle{ \frac{n!}{(s+1)!(n-s+1)!} \le \left( \frac{en}{s+1} \right)^{s+1}}\)
\(\displaystyle{ \frac{n!}{s!(n-s)!} \le \left( \frac{en}{s+1} \right)^{s+1}(s+1)(n-s+1)}\)
Więc jeśli spełniona będzie nierówność:
\(\displaystyle{ \left( \frac{en}{s} \right)^{s} \le \left( \frac{en}{s+1} \right)^{s+1}(s+1)(n-s+1)}\)
To teza
\(\displaystyle{ T(s+1)}\) też będzie spełniona ze względy na założenie
\(\displaystyle{ T(s)}\).
Nierówność ta przekształca się do:
\(\displaystyle{ \left( \frac{s+1}{s} \right)^{s} \le en(n-s+1)}\)
Zauważy, że wyrażanie po lewej stronie jest malejące ze względy na
\(\displaystyle{ s}\), więc wystarczy sprawdzić tylko graniczny przypadek
\(\displaystyle{ s=n}\) (po prawej) co daje:
\(\displaystyle{ \left( \frac{s+1}{s} \right)^{s} \le e}\)
Nierówność ta jest już znana i wynika z nierówności Bernoulliego. Tym samym kończąc dowód.
Mogę zapytać skąd wzięło się to pierwsze równanie?
Re: Szacowanie dwumianu Newtona
: 22 maja 2023, o 00:42
autor: Jan Kraszewski
Które równanie, jak tu są same nierówności?
JK
Re: Szacowanie dwumianu Newtona
: 22 maja 2023, o 13:21
autor: kaminie318
Jan Kraszewski pisze: ↑22 maja 2023, o 00:42
Które równanie, jak tu są same nierówności?
JK
Oczywiście, chodzi o pierwszą nierówność
Re: Szacowanie dwumianu Newtona
: 22 maja 2023, o 15:13
autor: Jan Kraszewski
kaminie318 pisze: ↑22 maja 2023, o 13:21
Oczywiście, chodzi o pierwszą nierówność
Pierwsza nierówność to teza kroku indukcyjnego, czyli coś, czego prawdziwość dowodzimy.
JK
Re: Szacowanie dwumianu Newtona
: 22 maja 2023, o 19:41
autor: kaminie318
Nie rozumiem tego rozwinięcia mianownika po opuszczeniu dwumianu Newtona, czy tam za \(\displaystyle{ s}\) podstawione jest po prostu \(\displaystyle{ s + 1}\)? Kłóci się to z mianownikiem wyrażenia po lewej stronie ponieważ wtedy powinno w nim być \(\displaystyle{ (s+1)!(n-s-1)!}\).