Sprawdzić, czy \(\displaystyle{ \sum_{i=0}^{k} {n_1 \choose i} {n_2 \choose k-i} = {n_1 + n_2 \choose k}}\).
W jaki sposób to pokazać?
Suma a symbol Newtona
- 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
Suma a symbol Newtona
Indukcja:
Baza jest łatwa do sprawdzenia.
Teza indukcyjna:(założenie wiemy jakie)
\(\displaystyle{ \sum_{i=0}^{k} {m+1 \choose i}{n \choose k-i}=\sum_{i=0}^{k}{m \choose i}{n \choose k-i}+\sum_{i=0}^{k}{m \choose i-1}{n \choose k-i}={m+n \choose k}+\sum_{i=0}^{k-1}{m \choose i}{n \choose k-i-1}={m+n \choose k}+{m+n \choose k-1}= {m+n+1 \choose k}}\)
Baza jest łatwa do sprawdzenia.
Teza indukcyjna:(założenie wiemy jakie)
\(\displaystyle{ \sum_{i=0}^{k} {m+1 \choose i}{n \choose k-i}=\sum_{i=0}^{k}{m \choose i}{n \choose k-i}+\sum_{i=0}^{k}{m \choose i-1}{n \choose k-i}={m+n \choose k}+\sum_{i=0}^{k-1}{m \choose i}{n \choose k-i-1}={m+n \choose k}+{m+n \choose k-1}= {m+n+1 \choose k}}\)