Szacowanie dwumianu Newtona
-
- 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
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.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 5
- Rejestracja: 16 kwie 2018, o 19:01
- Płeć: Kobieta
- Lokalizacja: Katowice
- Janusz Tracz
- Użytkownik
- Posty: 4088
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 81 razy
- Pomógł: 1399 razy
Szacowanie dwumianu Newtona
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.
\(\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.
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Szacowanie dwumianu Newtona
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}\).
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}\).
- Janusz Tracz
- Użytkownik
- Posty: 4088
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 81 razy
- Pomógł: 1399 razy
-
- Użytkownik
- Posty: 5
- Rejestracja: 16 kwie 2018, o 19:01
- Płeć: Kobieta
- Lokalizacja: Katowice
Szacowanie dwumianu Newtona
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.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.
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.
Powód: Używaj LaTeXa także do pojedynczych symboli.
- Janusz Tracz
- Użytkownik
- Posty: 4088
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 81 razy
- Pomógł: 1399 razy
Re: Szacowanie dwumianu Newtona
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}\)
\(\displaystyle{ \left( \frac{s+1}{s} \right)^{s} \le e \le en}\)
Szacowanie dwumianu Newtona
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...
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...
-
- Użytkownik
- Posty: 30
- Rejestracja: 22 maja 2023, o 00:02
- Płeć: Mężczyzna
- Podziękował: 3 razy
Re: Szacowanie dwumianu Newtona
Mogę zapytać skąd wzięło się to pierwsze równanie?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.
Ostatnio zmieniony 22 maja 2023, o 00:41 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Administrator
- Posty: 34370
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5208 razy
-
- Użytkownik
- Posty: 30
- Rejestracja: 22 maja 2023, o 00:02
- Płeć: Mężczyzna
- Podziękował: 3 razy
-
- Administrator
- Posty: 34370
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5208 razy
Re: Szacowanie dwumianu Newtona
Pierwsza nierówność to teza kroku indukcyjnego, czyli coś, czego prawdziwość dowodzimy.
JK
-
- Użytkownik
- Posty: 30
- Rejestracja: 22 maja 2023, o 00:02
- Płeć: Mężczyzna
- Podziękował: 3 razy
Re: Szacowanie dwumianu Newtona
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.