\(\displaystyle{ \sum_{k\,=\,0}^{n} {{n \choose k}2^{k}}\,=\,\sum_{k\,=\,0}^{n} {}\sum_{i\,=\,0}^{k} {{n \choose i}{n - i \choose k - i}\,=\,3^{n}}}\)
Obojetnie jakim sposobem:)
[Kombinatoryka] Udowodnij rowność z sumami
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
Wasilewski
- Użytkownik
- Posty: 3879
- Rejestracja: 10 gru 2007, o 20:10
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 36 razy
- Pomógł: 1194 razy
[Kombinatoryka] Udowodnij rowność z sumami
Zauważmy, że:
\(\displaystyle{ {n \choose i} {n - i \choose k-i} = \frac{n!}{i! (n-i)!} \frac{(n-i)!}{(n-k)! (k-i)!} \frac{k!}{k!} = {k \choose i}}\)
Zatem środkowa suma to:
\(\displaystyle{ \sum_{k=0}^{n} \sum_{i=0}^{k} {k \choose i} = \sum_{k=0}^{n} 2^{k} = \sum_{k=0}^{n} 2^{k} 1^{n-k} = (2+1)^{n} = 3^{n}}\)
\(\displaystyle{ {n \choose i} {n - i \choose k-i} = \frac{n!}{i! (n-i)!} \frac{(n-i)!}{(n-k)! (k-i)!} \frac{k!}{k!} = {k \choose i}}\)
Zatem środkowa suma to:
\(\displaystyle{ \sum_{k=0}^{n} \sum_{i=0}^{k} {k \choose i} = \sum_{k=0}^{n} 2^{k} = \sum_{k=0}^{n} 2^{k} 1^{n-k} = (2+1)^{n} = 3^{n}}\)