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}\)
Tożsamość (współczynniki dwumianowe)
-
Heniek1991
- Użytkownik
- Posty: 111
- Rejestracja: 14 paź 2010, o 16:58
- Płeć: Mężczyzna
- Lokalizacja: Lublin / Warszawa
- Podziękował: 1 raz
- Pomógł: 1 raz
Tożsamość (współczynniki dwumianowe)
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.
-
macciej91
- Użytkownik
- Posty: 105
- Rejestracja: 15 mar 2007, o 22:24
- Płeć: Mężczyzna
- Podziękował: 1 raz
- Pomógł: 10 razy
Tożsamość (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}\).
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}\).
-
Heniek1991
- Użytkownik
- Posty: 111
- Rejestracja: 14 paź 2010, o 16:58
- Płeć: Mężczyzna
- Lokalizacja: Lublin / Warszawa
- Podziękował: 1 raz
- Pomógł: 1 raz
Tożsamość (współczynniki dwumianowe)
Maciek z chęcią bym zobaczył twój sposób. Jeśli jesteś z MIMu to powiedz ile pkt dostałeś za to zadanie.
-
macciej91
- Użytkownik
- Posty: 105
- Rejestracja: 15 mar 2007, o 22:24
- Płeć: Mężczyzna
- Podziękował: 1 raz
- Pomógł: 10 razy
Tożsamość (współczynniki dwumianowe)
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
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
-
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
Tożsamość (współczynniki dwumianowe)
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}\)
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}\)