Udowodnij, że \(\displaystyle{ {n \choose s} \le {ne \choose s} ^{2} }\) dla wszystkich \(\displaystyle{ n,s \in \mathbb{N}}\).
Wiem, że już było takie zadanie na tej stronie, ale indukcyjnie szacowanie jest według \(\displaystyle{ s}\), a ja chciałbym według \(\displaystyle{ n}\) tylko nie wiem co dokładnie trzeba zmienić w tym.
Poniżej przesyłam link do innego rozwiązania:
Szacowanie dwumianu Newtona
Z góry dziękuję za pomoc
Dwumian Newtona
-
JohnnyBravo
- Użytkownik
- Posty: 3
- Rejestracja: 31 maja 2021, o 17:40
- Płeć: Mężczyzna
- wiek: 23
Dwumian Newtona
Ostatnio zmieniony 31 maja 2021, o 21:31 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Dwumian Newtona
Rozumiem, że pomyliłeś się w zapisie i miało być, jak w temacie, który zalinkowałeś, \(\displaystyle{ {n\choose s}\le \left(\frac{ne}{s}\right)^s}\).
Celem przeprowadzenia indukcji po \(\displaystyle{ n}\) tezę należy wzmocnić, inaczej nie idzie.
Można ją wzmocnić na przykład w ten sposób:
\(\displaystyle{ \frac{n^s}{s!}\le\left(\frac{ne}{s}\right)^s}\).
Wtedy indukcja po \(\displaystyle{ n\ge s}\) przy ustalonym \(\displaystyle{ s\in \NN}\) sprowadza się do tego, że
dla ciągów \(\displaystyle{ a_{n}=\frac{n^s}{s!}, \ b_{n}=\left(\frac{ne}{s}\right)^s}\) mamy
\(\displaystyle{ a_{s}=\frac{s^s}{s!}\le e^s=b_{s}}\) (znana nierówność \(\displaystyle{ k!\ge\left(\frac{k}{e}\right)^k}\), którą też można bez trudu dowieść indukcyjnie), a ponadto jest
\(\displaystyle{ \frac{a_{n+1}}{a_{n}}=\frac{b_{n+1}}{b_{n}}}\), więc przy założeniu, że dla pewnego \(\displaystyle{ n\in \NN, \ n\ge s}\)
jest \(\displaystyle{ a_{n}\le b_{n}}\), mamy \(\displaystyle{ a_{n+1}=a_{n}\cdot \frac{a_{n+1}}{a_{n}}=a_{n}\cdot \frac{b_{n+1}}{b_{n}}\le b_{n}\cdot \frac{b_{n+1}}{b_{n}}=b_{n+1}}\).
Celem przeprowadzenia indukcji po \(\displaystyle{ n}\) tezę należy wzmocnić, inaczej nie idzie.
Można ją wzmocnić na przykład w ten sposób:
\(\displaystyle{ \frac{n^s}{s!}\le\left(\frac{ne}{s}\right)^s}\).
Wtedy indukcja po \(\displaystyle{ n\ge s}\) przy ustalonym \(\displaystyle{ s\in \NN}\) sprowadza się do tego, że
dla ciągów \(\displaystyle{ a_{n}=\frac{n^s}{s!}, \ b_{n}=\left(\frac{ne}{s}\right)^s}\) mamy
\(\displaystyle{ a_{s}=\frac{s^s}{s!}\le e^s=b_{s}}\) (znana nierówność \(\displaystyle{ k!\ge\left(\frac{k}{e}\right)^k}\), którą też można bez trudu dowieść indukcyjnie), a ponadto jest
\(\displaystyle{ \frac{a_{n+1}}{a_{n}}=\frac{b_{n+1}}{b_{n}}}\), więc przy założeniu, że dla pewnego \(\displaystyle{ n\in \NN, \ n\ge s}\)
jest \(\displaystyle{ a_{n}\le b_{n}}\), mamy \(\displaystyle{ a_{n+1}=a_{n}\cdot \frac{a_{n+1}}{a_{n}}=a_{n}\cdot \frac{b_{n+1}}{b_{n}}\le b_{n}\cdot \frac{b_{n+1}}{b_{n}}=b_{n+1}}\).