Zadania z symbolem Newtona

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Nuna
Użytkownik
Użytkownik
Posty: 101
Rejestracja: 7 gru 2019, o 19:36
Płeć: Kobieta
wiek: 19
Podziękował: 58 razy

Zadania z symbolem Newtona

Post autor: Nuna »

Zad.1.
Znajdź zwartą postać sumy: \(\displaystyle{ \sum_{k=0}^{n} (-1)^{k} {n \choose k}^{2} }\).
Wskazówka: Skorzystaj z \(\displaystyle{ (1-x^{2})^n=(1-x)^{n}(1+x)^{n}}\)
Moja propozycja:
Ukryta treść:    
Zad.2. Udowodnij, że dla dowolnych liczb naturalnych \(\displaystyle{ k \le n}\) mamy:
\(\displaystyle{ \left( \frac{n}{k} \right)^{k} \le {n \choose k} \le \left( \frac{ne}{k} \right) ^{k} }\)

Tu za bardzo nie mam pomysłu, może indukcja? Ale wtedy po k czy 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: Zadania z symbolem Newtona

Post autor: Janusz Tracz »

Nuna pisze: 19 mar 2020, o 13:56 Zad.2. Udowodnij, że dla dowolnych liczb naturalnych \(\displaystyle{ k \le n}\) mamy:
\(\displaystyle{ \left( \frac{n}{k} \right)^{k} \le {n \choose k} }\)
Zauważmy, że gdy \(\displaystyle{ n \ge k}\) to dla każdego \(\displaystyle{ i\in \left\{ 0,1,...,k-1\right\} }\) zachodzi \(\displaystyle{ \frac{n}{k} \le \frac{n-i}{k-i} }\) dowód polega na sprawdzeniu, że \(\displaystyle{ n(k-i) \le k(n-i)}\) co sprawdza się do \(\displaystyle{ nk-in \le nk-ik}\) a to do założenia \(\displaystyle{ n \ge k}\). Zatem prawdą jest też:

\(\displaystyle{ \prod_{i=0}^{k-1} \frac{n}{k} \le \prod_{i=0}^{k-1} \frac{n-i}{k-i} }\)

co daje tezę.
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: Zadania z symbolem Newtona

Post autor: Premislav »

Co do pierwszego:
równość \(\displaystyle{ (1-x)^{n}(1+x)^{n}=\sum_{a=0}^{n}{n\choose a}(-x)^{a}\sum_{b=0}^{n}x^{b}}\)
jest przecież niepoprawna. Powinno być tak:
\(\displaystyle{ (1-x)^{n}(1+x)^{n}=\sum_{a=0}^{n}{n\choose a}(-x)^{a}\sum_{b=0}^{n}{n\choose b}x^{b}}\)
Natomiast samo porównanie współczynników przy \(\displaystyle{ x^{n}}\) to idealny pomysł, który zasugerowała zresztą ta wskazówka do zadania.
Z jednej strony ten współczynnik wynosi:
\(\displaystyle{ 0}\), gdy \(\displaystyle{ n}\) jest nieparzyste oraz \(\displaystyle{ (-1)^{\frac{n}{2}}{n\choose \frac{n}{2}}}\) gdy \(\displaystyle{ n}\) jest parzyste(z rozwinięcia \(\displaystyle{ \left(1-x^{2}\right)^{n}}\) ze wzoru dwumianowego).
Z drugiej strony korzystając z:
\(\displaystyle{ (1-x)^{n}(1+x)^{n}=\sum_{a=0}^{n}{n\choose a}(-x)^{a}\sum_{b=0}^{n}{n\choose b}x^{b}}\)
widzimy, że ten współczynnik wynosi \(\displaystyle{ \sum_{\left\{(a,b)\in \left\{0,1,\ldots n\right\}:a+b=n\right\}}^{}(-1)^{a}{n\choose a}{n\choose b}=\sum_{a=0}^{n}(-1)^{a}{n\choose a}{n\choose n-a}=\sum_{a=0}^{n}(-1)^{a}{n\choose a}^{2}}\)
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: Zadania z symbolem Newtona

Post autor: Janusz Tracz »

Nuna pisze: 19 mar 2020, o 13:56 Zad.2. Udowodnij, że dla dowolnych liczb naturalnych \(\displaystyle{ k \le n}\) mamy:
\(\displaystyle{ {n \choose k} \le \left( \frac{ne}{k} \right) ^{k} }\)
\(\displaystyle{ \text{Lemat.}}\) Dla dolnego \(\displaystyle{ k\in\NN}\) zachodzi \(\displaystyle{ k! \ge \left( \frac{k}{e} \right)^k }\) (to dość znane szacowanie silni)
dowód lematu:    
wtedy korzystając z lematu w drugiej (pierwsza zaś jest oczywista) nierówność mamy:

\(\displaystyle{ {n \choose k} \le \frac{n^k}{k!} \le \left( \frac{ne}{k} \right)^k }\)

czyli tezę.
Nuna
Użytkownik
Użytkownik
Posty: 101
Rejestracja: 7 gru 2019, o 19:36
Płeć: Kobieta
wiek: 19
Podziękował: 58 razy

Re: Zadania z symbolem Newtona

Post autor: Nuna »

Dziękuję za odpowiedzi, teraz jest już wszystko jasne
ODPOWIEDZ