Strona 1 z 3
Szacowanie dwumianu Newtona wykorzystując wzór
: 15 cze 2023, o 20:06
autor: kaminie318
Witam. Otrzymałem zadanie o następującej treści:
Udowodnij, że \(\displaystyle{ {n\choose s} \leqslant \left( \frac{ne}{s} \right) ^{s}}\) dla wszystkich 𝑛, 𝑠 ∈ ℕ korzystając z nierówności Bernoulliego
Wykorzystując internet i źródła otrzymałem następujące wyniki. Czy może ktoś ocenić rozwiązanie?
Teza:
\[{n\choose s} \leq \left( \frac{\text{ne}}{s} \right)^{s}\]
Założenia:
\[n\ \in N\ \land \text{s } \in N\ \land s \notin \{ 0\}\]
Dowód:
Aby udowodnić nierówność \[{n\choose s} \leq \left( \frac{\text{ne}}{s} \right)^{s}\] można wykorzystać wzór Stirlinga.
\[L = {n\choose s} = \frac{n!}{s!(n - s)!}\]
\[{P = \left( \frac{\text{ne}}{s} \right)}^{s} = \frac{({ne)}^{s}}{s^{s}}\]
Zastępujemy n! wzorem Stirlinga:
\[L = {n\choose s} = \frac{n!}{s!(n - s)!} \approx \frac{\sqrt{2\pi n}\left( \frac{n}{e} \right)^{n}}{\sqrt{2\pi s}\left( \frac{s}{e} \right)^{s}\sqrt{2\pi(n - s)}\left( \frac{n - s}{e} \right)^{n - s}} \approx \frac{\left( \frac{n}{e} \right)^{n}}{\left( \frac{s}{e} \right)^{s}\left( \frac{n - s}{e} \right)^{n - s}} = \left( \frac{n}{e} \right)^{s}\frac{{(n - s)}^{(n - s)}}{s^{s}}\]
Aby udowodnić nierówność
\[{n\choose s} \leq \left( \frac{\text{ne}}{s} \right)^{s}\]
wystarczy udowodnić, że
\[\left( \frac{n}{e} \right)^{s}\frac{{(n - s)}^{(n - s)}}{s^{s}} \geq 1\]
Możemy wykorzystać nierówność arytmetyczno-geometryczną która mówi że
dla dowolnych dodatnich liczb a1, a2, a3, ....., an ich średnia geometryczna
jest mniejsza lub równa średniej arytmetycznej.
Stosując tę nierówność do \[\left( \frac{n}{e} \right)^{s}\] oraz
\[\frac{{(n - s)}^{(n - s)}}{s^{s}}\] dla \(n - s\) razy otrzymujemy:
\[\left( \left( \frac{n}{e} \right)^{s}\frac{{(n - s)}^{(n - s)}}{s^{s}} \right)^{\frac{1}{n - s + 1}} \leq \frac{\left( \frac{n}{e} \right)^{s} + \frac{{(n - s)}^{(n - s)}}{s^{s}}}{n - s + 1}\]
Można teraz wykorzystać fakt, iż \(s^{s} \leq n^{s}\)aby pokazać, że
wyrażenie po prawej stronie jest mniejsze lub równe 1:
\[\frac{\left( \frac{n}{e} \right)^{s} + \frac{(n - s)^{(n - s)}}{s^{s}}}{n - s + 1} = \frac{\left( \frac{n}{e} \right)^{s} + \frac{(n - s)^{(n - s)}}{n^{s}}}{n - s + 1} \leq \frac{\left( \frac{n}{e} \right)^{s} + \frac{(n - s)^{(n - s)}}{n^{s}}}{n} \leq \frac{\left( \frac{n}{e} \right)^{s} + 1}{n} \leq \frac{\frac{n}{e} + 1}{n} < 1\]
CND, dlatego \[\left( \frac{n}{s} \right) \leq \left( \frac{\text{ne}}{s} \right)^{s}\] dla wszystkich 𝑛, 𝑠 ∈ ℕ
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 15 cze 2023, o 20:21
autor: a4karo
kaminie318 pisze: ↑15 cze 2023, o 20:06
Witam. Otrzymałem zadanie o następującej treści:
Udowodnij, że
\(\displaystyle{ {n\choose s} \leqslant \left( \frac{ne}{s} \right) ^{s}}\) dla wszystkich 𝑛, 𝑠 ∈ ℕ korzystając z nierówności Bernoulliego
Wykorzystując internet i źródła otrzymałem następujące wyniki. Czy może ktoś ocenić rozwiązanie?
Teza:
\[{n\choose s} \leq \left( \frac{\text{ne}}{s} \right)^{s}\]
Założenia:
\[n\ \in N\ \land \text{s } \in N\ \land s \notin \{ 0\}\]
Dowód:
Aby udowodnić nierówność \[{n\choose s} \leq \left( \frac{\text{ne}}{s} \right)^{s}\] można wykorzystać wzór Stirlinga.
\[L = {n\choose s} = \frac{n!}{s!(n - s)!}\]
\[{P = \left( \frac{\text{ne}}{s} \right)}^{s} = \frac{({ne)}^{s}}{s^{s}}\]
Zastępujemy n! wzorem Stirlinga:
\[L = {n\choose s} = \frac{n!}{s!(n - s)!} \approx \frac{\sqrt{2\pi n}\left( \frac{n}{e} \right)^{n}}{\sqrt{2\pi s}\left( \frac{s}{e} \right)^{s}\sqrt{2\pi(n - s)}\left( \frac{n - s}{e} \right)^{n - s}} \approx \frac{\left( \frac{n}{e} \right)^{n}}{\left( \frac{s}{e} \right)^{s}\left( \frac{n - s}{e} \right)^{n - s}} = \left( \frac{n}{e} \right)^{s}\frac{{(n - s)}^{(n - s)}}{s^{s}}\]
Pozbycie sie pierwiastków jest co najmniej podejrzane
Aby udowodnić nierówność
\[{n\choose s} \leq \left( \frac{\text{ne}}{s} \right)^{s}\]
wystarczy udowodnić, że
\[\left( \frac{n}{e} \right)^{s}\frac{{(n - s)}^{(n - s)}}{s^{s}} \geq 1\]
A możesz wytłumaczyć dlaczego? Przecież lewa strona to zgodnie z powyższym prawie
\(\displaystyle{ \binom{n}{s}}\)
Możemy wykorzystać nierówność arytmetyczno-geometryczną która mówi że
dla dowolnych dodatnich liczb a1, a2, a3, ....., an ich średnia geometryczna
jest mniejsza lub równa średniej arytmetycznej.
Stosując tę nierówność do \[\left( \frac{n}{e} \right)^{s}\] oraz
\[\frac{{(n - s)}^{(n - s)}}{s^{s}}\] dla \(n - s\) razy otrzymujemy:
\[\left( \left( \frac{n}{e} \right)^{s}\frac{{(n - s)}^{(n - s)}}{s^{s}} \right)^{\frac{1}{n - s + 1}} \leq \frac{\left( \frac{n}{e} \right)^{s} + \frac{{(n - s)}^{(n - s)}}{s^{s}}}{n - s + 1}\]
Można teraz wykorzystać fakt, iż \(s^{s} \leq n^{s}\)aby pokazać, że
wyrażenie po prawej stronie jest mniejsze lub równe 1:
\[\frac{\left( \frac{n}{e} \right)^{s} + \frac{(n - s)^{(n - s)}}{s^{s}}}{n - s + 1} = \frac{\left( \frac{n}{e} \right)^{s} + \frac{(n - s)^{(n - s)}}{n^{s}}}{n - s + 1} \leq \frac{\left( \frac{n}{e} \right)^{s} + \frac{(n - s)^{(n - s)}}{n^{s}}}{n} \leq \frac{\left( \frac{n}{e} \right)^{s} + 1}{n} \leq \frac{\frac{n}{e} + 1}{n} < 1\]
CND, dlatego \[\left( \frac{n}{s} \right) \leq \left( \frac{\text{ne}}{s} \right)^{s}\] dla wszystkich 𝑛, 𝑠 ∈ ℕ
Może być tak, że `a\approx b`, ale `a<c` a `c<b`, więc z nierówności dla wartości przybliżonej nie wynika nierówność dla wartości oryginalnej
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 15 cze 2023, o 22:58
autor: kaminie318
Posługuje się sztuczną inteligencją przy tym zadaniu, rzeczywiście niektóre rachunki są dziwne. Nie mogę skorzystać z indukcji matematycznej tylko muszę tym wzorem w związku z czym nie do końca wiem jak ugryźć to zadanie
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 15 cze 2023, o 23:30
autor: Janusz Tracz
Jeśli chcesz ze wzoru Stirlinga to robić zobacz:
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Wz%C3%B3r_Stirlinga#Szybko%C5%9B%C4%87_zbie%C5%BCno%C5%9Bci_i_oszacowanie_b%C5%82%C4%99du
z czego wynika
Co w połączeniu z nierównością, która wynika z prostej obserwacji
kończy zadanie:
Jeśli chcesz zrozumieć to rozwiązanie, udowodnij każdy z kroków.
PS wzór Stirlinga nie jest wymagany, można pierwszą nierówność wykazać indukcyjnie. Krok indukcyjny oprze się o dość znany fakt... który jest wnioskiem z nierówność Bernoulliego.
PPS
kaminie318 pisze: ↑15 cze 2023, o 22:58
Posługuje się sztuczną inteligencją przy tym zadaniu, rzeczywiście niektóre rachunki są dziwne.
Realna głupota jest lepsza od sztucznej inteligencji.
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 15 cze 2023, o 23:48
autor: kaminie318
Czytam odnośnik z wiki i nie rozumiem z czego wynikają hinty. Mogę prosić o bardziej szczegółowe nakierowanie? Czyli rozwiązanie które tu pokazałem w ogóle nie ma sensu?
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 16 cze 2023, o 08:40
autor: a4karo
kaminie318 pisze: ↑15 cze 2023, o 23:48
Czyli rozwiązanie które tu pokazałem w ogóle nie ma sensu?
Naprawdę sądzisz, że ten bełkot można nazwać rozwiązaniem?
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 16 cze 2023, o 11:10
autor: Janusz Tracz
kaminie318 pisze: ↑15 cze 2023, o 23:48
Czytam odnośnik z wiki i nie rozumiem z czego wynikają hinty. Mogę prosić o bardziej szczegółowe nakierowanie?
OK. Zignoruj wzór Stirlinga w takim razie i zrób pierwszy hint indukcją. Drugi hint nie wymaga nic poza obserwacją, że tak faktycznie jest.
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 16 cze 2023, o 15:11
autor: kaminie318
Chciałem wykorzystać indukcję w tym zadaniu, nota bene takie rozwiązanie już jest na stronie jednak prowadząca zabroniła wykorzystać mi indukcję sugerując wzór Stirlinga lub wzór Taylora
Dodano po 1 godzinie 9 minutach 27 sekundach:
kaminie318 pisze: ↑16 cze 2023, o 15:11
Janusz Tracz pisze: ↑16 cze 2023, o 11:10
kaminie318 pisze: ↑15 cze 2023, o 23:48
Czytam odnośnik z wiki i nie rozumiem z czego wynikają hinty. Mogę prosić o bardziej szczegółowe nakierowanie?
OK. Zignoruj wzór Stirlinga w takim razie i zrób pierwszy hint indukcją. Drugi hint nie wymaga nic poza obserwacją, że tak faktycznie jest.
Chciałem wykorzystać indukcję w tym zadaniu, nota bene takie rozwiązanie już jest na stronie jednak prowadząca zabroniła wykorzystać mi indukcję sugerując wzór Stirlinga lub wzór Taylora
Czy idę dobrym tokiem myśłenia? Chce doprowadzić nierówność z tezy do postaci z hintu 1. Oto moja obecna forma:
\[ \frac{n!}{(n-s)!} \leq n^{s}e^{s}\]
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 16 cze 2023, o 16:42
autor: Janusz Tracz
kaminie318 pisze: ↑16 cze 2023, o 16:21
Czy idę dobrym tokiem myśłenia?
Nie.
Zapomnij na chwilę o nierówności z zadania i skup się na pierwszym hincie. Do póki nie zrozumiesz dlaczego jest prawdziwy nie ma sensu iść do kolejnych. Hint do pierwszego hintu jest taki aby skorzystać z faktu:
\(\displaystyle{ s!={\sqrt {2\pi s}}\;\left({\frac {s}{e}}\right)^{s}e^{\lambda _{s}}}\)
dla pewnego
\(\displaystyle{ \frac {1}{12s+1}<\lambda _{n}< \frac {1}{12s}}\).
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 17 cze 2023, o 17:06
autor: kaminie318
Czy wynika to z faktu, że \(\displaystyle{ s^{s} \approx s! \Rightarrow s^{s} \le {\sqrt {2\pi s}}\;\left({\frac {s}{e}}\right)^{s}e^{\lambda _{s}}}\)
UPDATE: Czy wynika to po prostu z przybliżenia wzorów(Patrz wykres z wikipedii). Pierwszy wzór rozwinięcia wzoru Strilinga
\(\displaystyle{ s! \approx {\sqrt {2\pi s}}\;\left({\frac {s}{e}}\right)^{s}}\)
jest zdecydowanie bardziej popularny jednak mniej dokładny od
\(\displaystyle{ s! \approx {\sqrt {2\pi s}}\;\left({\frac {s}{e}}\right)^{s}e^{\lambda _{s}}}\)
Natomiast
\(\displaystyle{ s^{s} \approx s! }\)
W związku z czym następująca nierówność z hintu 1 jest prawdziwa
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 17 cze 2023, o 17:24
autor: Jan Kraszewski
kaminie318 pisze: ↑17 cze 2023, o 17:06Czy wynika to z faktu, że
\(\displaystyle{ s^{s} \approx s!}\)
To jest bardzo nieprawdziwe stwierdzenie:
\(\displaystyle{ \lim_{s\to\infty}\frac{s!}{s^s}=0}\).
JK
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 17 cze 2023, o 18:15
autor: kaminie318
Wywnioskowałem to na podstawie cytatu: "Przybliżenie Stirlinga „pierwszego rzędu”, \(\displaystyle{ s^{s} = s! }\) zostało użyte przez Maxa Plancka w jego artykule z roku 1901"
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 17 cze 2023, o 18:50
autor: Jan Kraszewski
Nie rób dowodów matematycznych opierając się na cytatach z Wikipedii.
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 17 cze 2023, o 18:54
autor: kaminie318
To co mi sugerujesz? Na jakiejś podstawie muszę to dowieść...
Próbuję teraz zrozumieć hint 2, masz jakieś wskazówki?
Re: Szacowanie dwumianu Newtona wykorzystując wzór
: 17 cze 2023, o 19:03
autor: Jan Kraszewski
kaminie318 pisze: ↑17 cze 2023, o 18:54
To co mi sugerujesz? Na jakiejś podstawie muszę to dowieść...
Na pewno nie na podstawie bardzo nieprawdziwych stwierdzeń.
kaminie318 pisze: ↑17 cze 2023, o 18:54Próbuję teraz zrozumieć hint 2, masz jakieś wskazówki?
Tak jak napisał
Janusz Tracz, jest to prosta obserwacja. Masz
\(\displaystyle{ \frac{n!}{(n-s)!}=\underbrace{(n-s+1)\cdot(n-s+2)\cdot\ldots\cdot(n-1)\cdot n}_{s\text{ składników}}.}\)
Teraz wystarczy każdy z tych składników prymitywnie oszacować z góry.
JK