Szacowanie dwumianu Newtona

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
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: 23 maja 2023, o 20:22skąd się to wszystko wzięło
Jeżeli nie rozumiesz, dlaczego zachodzi ta równość, to rada a4karo jest bardzo dobra.

Jeżeli nie rozumiesz, dlaczego takie (a nie inne) przekształcenie zostało wykonane, to odpowiedź brzmi: osoba wymyślająca dowód miała pomysł, że takie przekształcenie przyda się w dowodzie (i istotnie się przydało).

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 »

Dooobra, zrozumiałem :) Tam jest po prostu sztuczna jedynka, sprytne. Mam pytanko co do dalszego przekształcenia, skąd wzięła się prawa strona nierówności, czy mnożenie przez ten ułamek wynika z obustronnego mnożenia aby doprowadzić do wspólnej bazy tezy?

\(\displaystyle{ \binom{n}{s}\frac{n-s}{s+1}\le \left(\frac{en}{s}\right)^s\frac{n-s}{s+1}}\)
Jan Kraszewski
Administrator
Administrator
Posty: 34123
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: 23 maja 2023, o 23:38Mam pytanko co do dalszego przekształcenia, skąd wzięła się prawa strona nierówności, czy mnożenie przez ten ułamek wynika z obustronnego mnożenia aby doprowadzić do wspólnej bazy tezy?

\(\displaystyle{ \binom{n}{s}\frac{n-s}{s+1}\le \left(\frac{en}{s}\right)^s\frac{n-s}{s+1}}\)
To przejście to zastosowanie założenia indukcyjnego.

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 »

To jest przemnożęnie prawej strony nierówności z założenia indukcyjnego ponieważ dzieląc obustronnie wracamy się do pierwotnej postaci? Można traktować to mnożenie po prawej stronie również jako sztuczną jednykę?
Jan Kraszewski
Administrator
Administrator
Posty: 34123
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: 23 maja 2023, o 23:48To jest przemnożęnie prawej strony nierówności z założenia indukcyjnego ponieważ dzieląc obustronnie wracamy się do pierwotnej postaci?
Co?!
kaminie318 pisze: 23 maja 2023, o 23:48Można traktować to mnożenie po prawej stronie również jako sztuczną jednykę?
Nie wiem, coś Ty się tak uparł na "sztuczną jedynkę". To jakiś dziwny termin - przecież to są zwykłe przekształcenia algebraiczne.

Chcesz udowodnić, że

\(\displaystyle{ \binom{n}{s+1}\le \left(\frac{en}{s+1}\right)^{s+1}}\)

i ten dowód wygląda tak:

\(\displaystyle{ L=\binom{n}{s+1}=\frac{n!}{(s+1)!((n-s-1)!}=\frac{n!(n-s)}{s!(s+1)(n-s)!}=\binom{n}{s}\frac{n-s}{s+1}\,\red{\le}\, \left(\frac{en}{s}\right)^s\frac{n-s}{s+1}\,\blue{\le}\,\left(\frac{en}{s+1}\right)^{s+1} =P.}\)

Pozostaje tylko kwestia uzasadnienia jego poprawności. Pierwsza i trzecia równość to skorzystanie z definicji symbolu Newtona, druga równość to zwykłe przekształcenie algebraiczne, czerwona nierówność to wynik zastosowania założenia indukcyjnego (skoro \(\displaystyle{ \binom{n}{s}\le \left(\frac{en}{s}\right)^s}\), to \(\displaystyle{ \binom{n}{s}\frac{n-s}{s+1}\le\left(\frac{en}{s}\right)^s\frac{n-s}{s+1}}\) - pomnożyliśmy obie strony nierówności przez liczbę dodatnią \(\displaystyle{ \frac{n-s}{s+1}}\)), zaś uzasadnienie niebieskiej nierówności a4karo napisał osobno:

"A to jest równoważne nierówności \(\displaystyle{ \left(\frac{s+1}{s}\right)^s\le e\frac{n}{n-s}}\), która jest prawdziwa, bo \(\displaystyle{ \frac{n}{n-s}\ge 1}\)".

Oczywiście jest to dość skrótowe wyjaśnienie, które wymaga pewnej dodatkowej prostej wiedzy z analizy (o tym, że \(\displaystyle{ \left(1+\frac{1}{s}\right)^s\le e}\)).

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 »

Okej, dzięki wielkie. Już prawie wszystko rozumiem. Nie mogę pojąć jedynie skąd uzasadnienie niebieskiej nierówności, chodzi o to przekształcenie, skąd ta równoważność: "A to jest równoważne nierówności \(\displaystyle{ \left(\frac{s+1}{s}\right)^s\le e\frac{n}{n-s}}\), która jest prawdziwa, bo \(\displaystyle{ \frac{n}{n-s}\ge 1}\)".

Nie mogę znaleźć nigdzie tej wartości dla liczby eulera w internecie, skąd wynika ta nierówność?: \(\displaystyle{ \left(1+\frac{1}{s}\right)^s\le e}\) W internecie podana jest stała: \(\displaystyle{ \left(1+\frac{1}{s}\right)^s = e}\) . Skąd to założenie że e może być większe od wyrażenia po lewej stronie?

Dodano po 2 godzinach 44 minutach 14 sekundach:
UPDATE: Nie mogę robić tego indukcją, prowadząca mówi że indukcja w tym wypadku nie ma sensu ponieważ trzeba podstawiać za n :/ Muszę zrobić wzorem Tailora lub Stirlinga
Ostatnio zmieniony 27 maja 2023, o 22:14 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
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: 27 maja 2023, o 14:11Nie mogę pojąć jedynie skąd uzasadnienie niebieskiej nierówności, chodzi o to przekształcenie, skąd ta równoważność: "A to jest równoważne nierówności \(\displaystyle{ \left(\frac{s+1}{s}\right)^s\le e\frac{n}{n-s}}\), która jest prawdziwa, bo \(\displaystyle{ \frac{n}{n-s}\ge 1}\)".

Nie mogę znaleźć nigdzie tej wartości dla liczby eulera w internecie, skąd wynika ta nierówność?: \(\displaystyle{ \left(1+\frac{1}{s}\right)^s\le e}\) W internecie podana jest stała: \(\displaystyle{ \left(1+\frac{1}{s}\right)^s = e}\) . Skąd to założenie że e może być większe od wyrażenia po lewej stronie?
Jeśli w internecie "podana jest stała: \(\displaystyle{ \left(1+\frac{1}{s}\right)^s = e}\)", to jest to bardzo zły internet, bo to nieprawda. Zmień na jakiś lepszy...

Natomiast prawdą jest, że \(\displaystyle{ \lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n = e}\) i wiadomo (to jest wiedza z analizy, o której pisałem), że ciąg \(\displaystyle{ \left(1+\frac{1}{n}\right)^n}\) jest rosnący, zatem jego granica jest większa od każdego jego wyrazu.
kaminie318 pisze: 27 maja 2023, o 14:11 Nie mogę robić tego indukcją, prowadząca mówi że indukcja w tym wypadku nie ma sensu ponieważ trzeba podstawiać za n
Indukcja ma sens, bo to jest indukcja po \(\displaystyle{ s}\), a nie po \(\displaystyle{ n}\). Ale jak nie możesz, to trudno.

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 »

Jak udowodnić postawioną tezę wzorem Strilinga? Jakieś wskazówki?
aleks3650
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 18 lis 2023, o 23:56
Płeć: Mężczyzna
wiek: 23

Re: Szacowanie dwumianu Newtona

Post autor: aleks3650 »

podpinam się do pytania
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: Szacowanie dwumianu Newtona

Post autor: janusz47 »

\(\displaystyle{ {n \choose s} = \frac{n!}{s!(n-s)!} \leq \frac{n!}{s!} \leq \frac{n^{s}}{s!} \leq \frac{n^{s}}{\sqrt{2\pi s}\left(\frac{s}{e}\right)^{s}} = \left(\frac{ne}{s}\right )^{s}.}\)
aleks3650
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 18 lis 2023, o 23:56
Płeć: Mężczyzna
wiek: 23

Re: Szacowanie dwumianu Newtona

Post autor: aleks3650 »

skąd się wzięło \(\displaystyle{ \frac{n^{s} }{ \sqrt{2 π s} (\frac{s}{e}) ^{s} } }\) ?

Udało mi się z lewej strony dojść do \(\displaystyle{ \frac{ (\frac{n}{n-s}) ^{n+1} }{\sqrt{2 π s} (\frac{s}{n-s}) ^{s} } }\) i nie wiem co dalej
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: Szacowanie dwumianu Newtona

Post autor: janusz47 »

Ze wzoru Stirlinga.
ODPOWIEDZ