Sumy z dwumianem Newtona (3zad.)

[Konikov]

• \(\displaystyle{ \sum_{k=0}^{\lfloor n/2 \rfloor} {n \choose 2k} 2^{2k}}\)

• \(\displaystyle{ \sum_{k=0}^{m} (-1)^k {n \choose k} {n \choose m - k}}\)

• Przedstawić jako wsp. dwumianowy: \(\displaystyle{ \sum_{i_{n} = 0}^{m} \sum_{i_{n-1} = 0}^{i_n} ... \sum_{i_{2} = 0}^{i_3} \sum_{i_{1} = 0}^{i_2} \sum_{i_{0} = 0}^{i_1} 1}\)

Z góry dzięki ;]

[Dumel]

1. rozpisz z dwumianu \(\displaystyle{ (2-1)^n}\) oraz \(\displaystyle{ (2+1)^n}\)
2. splot funkcji tworzących
3. kombinacje z powtórzeniami

[Konikov]

1. \(\displaystyle{ (2+1)^n = (1+2)^n = \sum_{k \ge 0}^{} {n \choose k} 2^k}\), ale \(\displaystyle{ (2-1)^n}\)? \(\displaystyle{ \sum_{k \ge 0}^{} (-1)^k {n \choose k} 2^k}\)? Dlaczego?

[Crizz]

1. \(\displaystyle{ (2+1)^n = (1+2)^n = \sum_{k \ge 0}^{} {n \choose k} 2^k}\), ale \(\displaystyle{ (2-1)^n}\)? \(\displaystyle{ \sum_{k \ge 0}^{} (-1)^k {n \choose k} 2^k}\)?

\(\displaystyle{ \sum_{k \ge 0}^{}}\) to nie trochę za dużo? Czytelniej będzie zapisać:

\(\displaystyle{ (2+1)^n = (1+2)^n = \sum_{k=0}^{n} {n \choose k} 2^k}\)
\(\displaystyle{ (2-1)^n=\sum_{k=0}^{n} (-1)^k {n \choose k} 2^k}\)

No to teraz dodaj stronami.

[Konikov]

Okay, dzięki wielkie. ;] Ale trzeciego nie potrafię, czy mógłby ktoś po kolei to rozwiązać? ;]

[Zordon]

Ta suma oblicza ile jest ciągów \(\displaystyle{ (i_0,...,i_n)}\) spełniających \(\displaystyle{ 0\leq i_0\leq i_1\leq...\leq i_n\leq m}\).

[Konikov]

Przepraszam, drugiego ze splotem ;] Ale dzięki, także pomogłeś ;]

[Zordon]

No to rozważmy wielomiany:
\(\displaystyle{ W(x)= \sum_{k=0}^{n} {n \choose k} x^k(-1)^k=(1-x)^n}\)
\(\displaystyle{ V(x)= \sum_{k=0}^{n} {n \choose k} x^k=(1+x)^n}\)

Jaki współczynnik stoi przy \(\displaystyle{ x^m}\) w \(\displaystyle{ W(x) \cdot V(x)}\)?

[Konikov]

@Crizz

\(\displaystyle{ \sum_{k \ge 0}^{} (-1)^k {n \choose k} 2^k = \sum_{k = 0}^{n} (-1)^k {n \choose k} 2^k}\)

Im mniej znaczków, tym przejrzyściej ;]

(1 zad.) W uogólnieniu reguła której nie znałem przedstawia się tak:

\(\displaystyle{ (m + 1)^n = \sum_{k \ge 0}^{} {n \choose k} m^k}\)
\(\displaystyle{ (m - 1)^n = \sum_{k \ge 0}^{} (-1)^k{n \choose k} m^k}\)-- 23 sierpnia 2010, 20:42 --

No to rozważmy wielomiany:
\(\displaystyle{ W(x)= \sum_{k=0}^{n} {n \choose k} x^k(-1)^k=(1-x)^n}\)
\(\displaystyle{ V(x)= \sum_{k=0}^{n} {n \choose k} x^k=(1+x)^n}\)

Jaki współczynnik stoi przy \(\displaystyle{ x^m}\) w \(\displaystyle{ W(x) \cdot V(x)}\)?

Wychodzi idealnie to, co trzeba. Mamy \(\displaystyle{ W(x)*V(x) = \sum_{m}^{} \left( \sum_{k=0}^{m} (-1)^k {n \choose k} {n \choose m - k}\right) x^m = (1+x^2)^n}\)

Tylko jak się dostać do zwartej postaci owych czynników? Szereg Maclaurina chyba się nie przyda, zbyt wielkie pochodne wychodzą i nie widzę oczywistego patternu na ich dowolne wyprowadzenie. Może bez funkcji tworzących jakoś wyjdzie? W sumie zadanie z działu przed nimi ;]

[Dumel]

mamy tu pewną sprzeczność:
stąd wynika że wiesz co to jest wzór dwumienny Newtona:

uogólnieniu reguła której nie znałem przedstawia się tak:
\(\displaystyle{ (m + 1)^n = \sum_{k \ge 0}^{} {n \choose k} m^k}\)
\(\displaystyle{ (m - 1)^n = \sum_{k \ge 0}^{} (-1)^k{n \choose k} m^k}\)

a stąd że jednak nie:

Wychodzi idealnie to, co trzeba. Mamy \(\displaystyle{ W(x)*V(x) = \sum_{m}^{} \left( \sum_{k=0}^{m} (-1)^k {n \choose k} {n \choose m - k}\right) x^m = (1+x^2)^n}\)
Tylko jak się dostać do zwartej postaci owych czynników?

[Konikov]

Oprócz tego, że powinien być minus: \(\displaystyle{ (1\underline{-}x^2)^n}\) nie wiem, na czym polegał mój błąd (lub oczywistość dalszych działań). Mniej enigmatyczne odpowiedzi są w cenie ;]

[Zordon]

co stoi przy \(\displaystyle{ x^m}\) w wielomianie \(\displaystyle{ (1+x^2)^n}\)?

[Konikov]

Jak napisałem powyżej, przy \(\displaystyle{ x^m}\) stoi: \(\displaystyle{ \sum_{k=0}^{m} (-1)^k {n \choose k} {n \choose m - k}}\)

\(\displaystyle{ (1-x^2)^n}\), a nie \(\displaystyle{ (1+x^2)^n}\)

Jak teraz skorzystać z owego splotu i doprowadzić do postaci zwartej (pochodna \(\displaystyle{ (1-x^2)^n}\) m-tego stopnia podzielona przez \(\displaystyle{ m!}\) raczej nie wchodzi w grę...)?

Prawdopodobnie mój błąd polega na braku zaznaczenia, że w 2 pierwszych zadaniach chodzi jedynie o postać zwartą.

[Zordon]

OK, rozpisz \(\displaystyle{ (1-x^2)^n}\) z dwumianu Newtona i zobacz co stoi przy \(\displaystyle{ x^m}\)

[Konikov]

Sweet! ;D

\(\displaystyle{ (1-x^2)^n = \sum_{k \ge 0} {n \choose k} (-x^2)^{n-k} = \sum_{k \ge 0} {n \choose k} (-1)^k \cdot x^{2k}}\)

Dla nieparzystych \(\displaystyle{ m}\) wychodzi 0.

Dla parzystych: \(\displaystyle{ {n \choose \frac{m}{2} } (-1)^{\frac{m}{2}}}\), testy wypadają zgodnie z napisanym przeze mnie programem wyliczającym pierwotną sumę ;]