Matematyka.pl

Proszę o pomoc w udowodnieniu następującej tożsamości:

\(\displaystyle{ \sum_{j=0}^{k} {n \choose j} = \sum_{j=0}^{k} {n-j-1 \choose k-j}2^{j}}\)

\(\displaystyle{ 0 \le k \le n-1}\)

Miałem to w tym roku na egzaminie, to idzie z indukcji po n. Do tego trzeba pamiętać wzór rekurencyjny na współczynniki dwumianowe.

Można bez indukcji, tylko trzeba wzorki znać lub umieć wyprowadzić.
Polecam przyjrzeć się szczególnie \(\displaystyle{ \sum_{0 \le k \le l}\binom{l-k}{m}\binom{q+k}{n}=\binom{l+q+1}{m+n+1},l,m \ge 0, n \ge q \ge 0}\).

Maciek z chęcią bym zobaczył twój sposób. Jeśli jesteś z MIMu to powiedz ile pkt dostałeś za to zadanie.

Przyłączam się do prośby.

15
Proszę bardzo, oto całe rozwiązanie:
\(\displaystyle{ \sum_{j=0}^{k}\binom{n-j-1}{k-j}2^j=\sum_{j=0}^{k}\left (\binom{n-j-1}{k-j}\cdot\sum_{i=0}^{j}\binom{j}{i}\right )=\sum_{j=0}^{k}\sum_{i=0}^{j}\left (\binom{n-j-1}{k-j}\cdot\binom{j}{i}\right )=\sum_{j=0}^{k}\sum_{i=0}^{j}\left (\binom{n-j-1}{n-k-1}\cdot\binom{j}{i}\right )=\sum_{i=0}^{k}\sum_{j=0}^{n-1}\left (\binom{n-j-1}{n-k-1}\cdot\binom{j}{i}\right )=\sum_{i=0}^{k}\binom{n}{n-k+i}=\sum_{i=0}^{k}\binom{n}{k-i}=\sum_{i=0}^{k}\binom{n}{i}}\)
No i dostajemy to co chcieliśmy. Dodatkowo, należałoby uzasadnić w momencie gdy zmieniam między sobą sumy, dlaczego nic się wtedy nie psuje. No i oczywiście wzór z którego korzystamy

Rozważmy \(\displaystyle{ X = \{0,...,n-1\}}\), niech \(\displaystyle{ \mathbf{P}_k(X)}\) oznacza zbiór podzbiorów co najwyżej \(\displaystyle{ k}\) elementowych zbioru \(\displaystyle{ X}\), niech \(\displaystyle{ \phi(j,Y) = |\{i \ | \ i > j, \ i \in Y\}|}\).

Lewa strona równości jest równa \(\displaystyle{ |\mathbf{P}_k(X)|}\), spróbujemy podzielić podzbiory co najwyżej \(\displaystyle{ k}\) elementowe zbioru \(\displaystyle{ X}\) na pewne klasy, w tym celu zdefiniujmy relację na \(\displaystyle{ \mathbf{P}_k(X)}\)

\(\displaystyle{ I \sim J \quad \iff \quad \exists_{j \leq k, \ j \not \in I \cup J} \ \phi(j,I) = \phi(j,J) = k-j}\)

Można sprawdzić, że jest to relacja równoważnośći, która posiada \(\displaystyle{ k+1}\) klas abstrakcji \(\displaystyle{ A_j}\), gdzie \(\displaystyle{ A_j}\) jest zbiorem podzbiorów które nie zawierają \(\displaystyle{ j}\) i mają dokładnie \(\displaystyle{ k-j}\) elementów większych od \(\displaystyle{ j}\). W celu policzenia takich podzbiorów wybierzmy do naszego podzbioru \(\displaystyle{ k-j}\) elementów z \(\displaystyle{ \{j+1,...,n-1\}}\) na \(\displaystyle{ {n-1-j \choose k-j}}\) sposobów i dołóżmy dowolny podzbiór \(\displaystyle{ \{0,...,j-1\}}\) na \(\displaystyle{ 2^j}\) sposobów, więc \(\displaystyle{ |A_j|={n-1-j \choose k-j} 2^j}\), zatem

\(\displaystyle{ \sum_{j=0}^k {n \choose j} = |\mathbf{P}_k(X)| = \sum_{j=0}^k |A_k| =\sum_{j=0}^k {n-1-j \choose k-j} 2^j}\)

Dzięki!