Policz na 2 sposoby ile jest możliwości wyboru 3. rozdziałów z książki mającej ich \(\displaystyle{ n+1}\) , aby udowodnić tożsamość
\(\displaystyle{ \sum^{n}_{k=2} {k \choose 2} = {n+1 \choose 3}}\) .
Wyprowadź z niej wzór na sumę kwadratów. Uogólnij tożsamość tak, by otrzymać wzór na \(\displaystyle{ {n+1 \choose m}}\) .
Rozw:
1*: \(\displaystyle{ {n+1 \choose 3}}\)
2*: \(\displaystyle{ {n+1 \choose 1} +{n \choose 1} + {n-1 \choose 1}}\)
Ta tożsamość wygląda tak a nie inaczej, ale czy w jej zapisie nie ma błędu? (chcę się upewnić)
Mały dowodzik
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Mały dowodzik
Nie rozumiem tego, co piszesz odnośnie rozwiązania zadania. Ja bym od razu udowadniał ogólniejszą tożsamość, o której napomknięto w treści zadania. A mianowicie,
\(\displaystyle{ \sum_{k=m-1}^{n}{k \choose m-1} ={n+1\choose m}}\)
gdzie \(\displaystyle{ m,n \in \NN}\) i \(\displaystyle{ m\le n+1}\).
Można to łatwo udowodnić indukcją po \(\displaystyle{ n\ge m-1}\) przy ustalonym \(\displaystyle{ m}\), aczkolwiek można też napisać interpretację kombinatoryczną. Interpretacja prawej strony jest dość jasna: \(\displaystyle{ {n+1\choose m}}\) podzbiorów m-elementowych zbioru o \(\displaystyle{ n+1}\) elementach.
Po lewej stronie patrzymy na to trochę inaczej:
ustawmy te elementy w szeregu i je ponumerujmy i pomyślmy sobie o numerze, jaki będzie miał ostatni element, który dołączymy do naszego podzbioru m-elementowego. Jeśli będzie on miał numer \(\displaystyle{ m}\), to wybieramy \(\displaystyle{ m-1}\) spośród \(\displaystyle{ m-1}\) wcześniejszych, jeśli będzie on miał numer \(\displaystyle{ m+1}\), to wybieramy \(\displaystyle{ m-1}\) spośród m wcześniejszych na \(\displaystyle{ {m-1 \choose m}}\) sposobów itd.-- 26 lut 2018, o 23:59 --Tak jeszcze dodam, że wspomnienie rozdziałów książki służyło właśnie temu, żeby łatwiej było wpaść na ten pomysł (dość naturalne jest, że rozdziały mają kolejność).
\(\displaystyle{ \sum_{k=m-1}^{n}{k \choose m-1} ={n+1\choose m}}\)
gdzie \(\displaystyle{ m,n \in \NN}\) i \(\displaystyle{ m\le n+1}\).
Można to łatwo udowodnić indukcją po \(\displaystyle{ n\ge m-1}\) przy ustalonym \(\displaystyle{ m}\), aczkolwiek można też napisać interpretację kombinatoryczną. Interpretacja prawej strony jest dość jasna: \(\displaystyle{ {n+1\choose m}}\) podzbiorów m-elementowych zbioru o \(\displaystyle{ n+1}\) elementach.
Po lewej stronie patrzymy na to trochę inaczej:
ustawmy te elementy w szeregu i je ponumerujmy i pomyślmy sobie o numerze, jaki będzie miał ostatni element, który dołączymy do naszego podzbioru m-elementowego. Jeśli będzie on miał numer \(\displaystyle{ m}\), to wybieramy \(\displaystyle{ m-1}\) spośród \(\displaystyle{ m-1}\) wcześniejszych, jeśli będzie on miał numer \(\displaystyle{ m+1}\), to wybieramy \(\displaystyle{ m-1}\) spośród m wcześniejszych na \(\displaystyle{ {m-1 \choose m}}\) sposobów itd.-- 26 lut 2018, o 23:59 --Tak jeszcze dodam, że wspomnienie rozdziałów książki służyło właśnie temu, żeby łatwiej było wpaść na ten pomysł (dość naturalne jest, że rozdziały mają kolejność).