Szacowanie dwumianu Newtona

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
tece
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 9 mar 2008, o 19:48
Płeć: Mężczyzna
Lokalizacja: gorzow wlkp
Podziękował: 1 raz
Pomógł: 1 raz

Szacowanie dwumianu Newtona

Post 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}\).
Ostatnio zmieniony 17 maja 2018, o 23:03 przez SlotaWoj, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
paluch102
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 7 kwie 2010, o 18:19
Płeć: Mężczyzna
Lokalizacja: Śląsk

Szacowanie dwumianu Newtona

Post autor: paluch102 »

Witam
Ponawiam prośbę o jasne wytłumaczenie tego zadanka.
popiszsieplay
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 16 kwie 2018, o 19:01
Płeć: Kobieta
Lokalizacja: Katowice

Szacowanie dwumianu Newtona

Post autor: popiszsieplay »

Również ponawiam prośbę o rozwiązanie zadania
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Szacowanie dwumianu Newtona

Post 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.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Szacowanie dwumianu Newtona

Post 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}\).
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Szacowanie dwumianu Newtona

Post autor: Janusz Tracz »

Fajne ale złotego szpadla Ci nie oddam!
popiszsieplay
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 16 kwie 2018, o 19:01
Płeć: Kobieta
Lokalizacja: Katowice

Re: Szacowanie dwumianu Newtona

Post autor: popiszsieplay »

Dziękuję, chłopaki!
Wysu
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 30 kwie 2019, o 09:51
Płeć: Mężczyzna
Lokalizacja: Sosnowiec

Szacowanie dwumianu Newtona

Post 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ź.
Ostatnio zmieniony 30 kwie 2019, o 12:11 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa także do pojedynczych symboli.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Szacowanie dwumianu Newtona

Post 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}\)
Wysu
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 30 kwie 2019, o 09:51
Płeć: Mężczyzna
Lokalizacja: Sosnowiec

Szacowanie dwumianu Newtona

Post 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...
kaminie318
Użytkownik
Użytkownik
Posty: 30
Rejestracja: 22 maja 2023, o 00:02
Płeć: Mężczyzna
Podziękował: 3 razy

Re: Szacowanie dwumianu Newtona

Post 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?
Ostatnio zmieniony 22 maja 2023, o 00:41 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Szacowanie dwumianu Newtona

Post autor: Jan Kraszewski »

Które równanie, jak tu są same nierówności?

JK
kaminie318
Użytkownik
Użytkownik
Posty: 30
Rejestracja: 22 maja 2023, o 00:02
Płeć: Mężczyzna
Podziękował: 3 razy

Re: Szacowanie dwumianu Newtona

Post 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ść
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Szacowanie dwumianu Newtona

Post 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
kaminie318
Użytkownik
Użytkownik
Posty: 30
Rejestracja: 22 maja 2023, o 00:02
Płeć: Mężczyzna
Podziękował: 3 razy

Re: Szacowanie dwumianu Newtona

Post 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)!}\).
Ostatnio zmieniony 22 maja 2023, o 22:13 przez Jan Kraszewski, łącznie zmieniany 1 raz.
ODPOWIEDZ