Wyszło mi przy okazji jednego zadania, ale pewnie da się jakoś łatwo:
\(\displaystyle{ \sum_{k=1}^{n} {2n-1-k \choose n-1} 2^k = 2^{2n-1}}\)
[Kombinatoryka] Tożsamość kombinatoryczna
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.
-
jerzozwierz
- Użytkownik
- Posty: 523
- Rejestracja: 22 lut 2009, o 10:13
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 8 razy
- Pomógł: 42 razy
-
King James
- Użytkownik
- Posty: 150
- Rejestracja: 19 kwie 2007, o 22:52
- Płeć: Mężczyzna
- Lokalizacja: Biłgoraj/Kraków
- Pomógł: 39 razy
[Kombinatoryka] Tożsamość kombinatoryczna
Dla wygody zamienimy \(\displaystyle{ n}\) na \(\displaystyle{ n+1}\), następnie \(\displaystyle{ k}\) na \(\displaystyle{ n-k}\) i podzielimy tożsamość przez \(\displaystyle{ 2}\) otrzymując
\(\displaystyle{ \sum_{k=0}^{n} {n+k \choose n} 2^{n-k} = \frac{1}{2}2^{2n+1}}\)
Policzymy liczbę podzbiorów zbioru \(\displaystyle{ \{0,...,2n\}}\) które zawierają co najmniej \(\displaystyle{ n+1}\) elementów (jest ich tyle samo co podzbiorów zawierających co najwyżej \(\displaystyle{ n}\) elementów). Zatem mamy ich \(\displaystyle{ \frac{1}{2}2^{2n+1}}\).
Następnie policzymy liczbę takich podzbiorów przy ustalonym co do wielkości \(\displaystyle{ n+1}\) elemencie, powiedzmy równym \(\displaystyle{ n+k}\), dla \(\displaystyle{ k \in \{0,...,n\}}\). Dowolny taki podzbiór powstaje przez wybranie \(\displaystyle{ n}\) elementów ze zbioru \(\displaystyle{ \{0,...,n+k-1\}}\), dorzucenie \(\displaystyle{ n+k}\) i dołożenie dowolnego podzbioru zbioru \(\displaystyle{ \{n+k+1,...,2n\}}\), zatem takich podzbiorów mamy \(\displaystyle{ {n+k \choose n} 2^{n-k}}\), sumując po \(\displaystyle{ k}\) otrzymujemy tożsamość.
\(\displaystyle{ \sum_{k=0}^{n} {n+k \choose n} 2^{n-k} = \frac{1}{2}2^{2n+1}}\)
Policzymy liczbę podzbiorów zbioru \(\displaystyle{ \{0,...,2n\}}\) które zawierają co najmniej \(\displaystyle{ n+1}\) elementów (jest ich tyle samo co podzbiorów zawierających co najwyżej \(\displaystyle{ n}\) elementów). Zatem mamy ich \(\displaystyle{ \frac{1}{2}2^{2n+1}}\).
Następnie policzymy liczbę takich podzbiorów przy ustalonym co do wielkości \(\displaystyle{ n+1}\) elemencie, powiedzmy równym \(\displaystyle{ n+k}\), dla \(\displaystyle{ k \in \{0,...,n\}}\). Dowolny taki podzbiór powstaje przez wybranie \(\displaystyle{ n}\) elementów ze zbioru \(\displaystyle{ \{0,...,n+k-1\}}\), dorzucenie \(\displaystyle{ n+k}\) i dołożenie dowolnego podzbioru zbioru \(\displaystyle{ \{n+k+1,...,2n\}}\), zatem takich podzbiorów mamy \(\displaystyle{ {n+k \choose n} 2^{n-k}}\), sumując po \(\displaystyle{ k}\) otrzymujemy tożsamość.