Matematyka.pl

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}}\)

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ść.