Mógłby mi ktoś wyjaśnić, skąd bierze się ten wzór:
\(\displaystyle{ \sum_{k \in Z} {n \choose k} {m \choose p-k} = {n+m \choose p}}\)-- 29 sty 2013, o 15:52 --\(\displaystyle{ n,m \in N}\) i \(\displaystyle{ p \in Z}\)
skąd bierze się wzór
- zidan3
- Użytkownik
- Posty: 694
- Rejestracja: 9 kwie 2011, o 10:05
- Płeć: Mężczyzna
- Lokalizacja: Lbn
- Podziękował: 9 razy
- Pomógł: 112 razy
skąd bierze się wzór
Wiemy, że \(\displaystyle{ (1+x)^n=\sum_{k=0}^{n} {n \choose k} x^k}\). Zatem oczywistym jest
\(\displaystyle{ (1+x)^{n+m}=(1+x)^n \cdot (1+x)^m=\left( \sum_{k=0}^{n} {n \choose k} x^k\right) \left( \sum_{k=0}^{m} {m \choose k} x^k\right)}\)
Więc mamy równość wielomianów. Porównajmy współczynniki przy \(\displaystyle{ x^k}\) po obu stronach, stąd dostajemy
\(\displaystyle{ {n+m \choose k} x^k=\sum_{i=0}^{k} {m \choose i} x^i \cdot {n \choose k-i}x^{k-i}=\sum_{i=0}^{k} {m \choose i} {n \choose k-i} x^k}\) dzieląc obustronnie przez \(\displaystyle{ x^k}\) otrzymujemy tezę
\(\displaystyle{ \sum_{i=0}^{k} {m \choose i} {n \choose k-i}= {n+m \choose k}}\)
Można również udowodnić to indukcyjnie.
\(\displaystyle{ (1+x)^{n+m}=(1+x)^n \cdot (1+x)^m=\left( \sum_{k=0}^{n} {n \choose k} x^k\right) \left( \sum_{k=0}^{m} {m \choose k} x^k\right)}\)
Więc mamy równość wielomianów. Porównajmy współczynniki przy \(\displaystyle{ x^k}\) po obu stronach, stąd dostajemy
\(\displaystyle{ {n+m \choose k} x^k=\sum_{i=0}^{k} {m \choose i} x^i \cdot {n \choose k-i}x^{k-i}=\sum_{i=0}^{k} {m \choose i} {n \choose k-i} x^k}\) dzieląc obustronnie przez \(\displaystyle{ x^k}\) otrzymujemy tezę
\(\displaystyle{ \sum_{i=0}^{k} {m \choose i} {n \choose k-i}= {n+m \choose k}}\)
Można również udowodnić to indukcyjnie.