Udowodnij kombinatorycznie

[max123321]

Udowodnij kombinatorycznie tożsamość:
\(\displaystyle{ \sum_{k=0}^{n} {n-k \choose m} {k \choose m} = {n+1 \choose 2m+1}}\)

Należy opisać pewną sytuację, zadać pytanie typu "ile czegoś jest", a następnie odpowiedzieć na nie na dwa sposoby, uzyskując odpowiednio lewą i prawą stronę równości.

Jak to zrobić? Jakaś wskazówka?

[Tmkk]

Tak naprawdę ta suma po lewej jest od \(\displaystyle{ k=m}\) do \(\displaystyle{ k = n-m}\).

Podpowiedź:
Prawa strona to po prostu wybór \(\displaystyle{ 2m+1}\) spośród \(\displaystyle{ n+1}\) rzeczy.
Lewa strona: ustaw te \(\displaystyle{ n+1}\) rzeczy w rządku i popatrz na \(\displaystyle{ k+1}\)-szą rzecz.

[max123321]

Niestety nie wiem, nie umiem sobie tego chyba wyobrazić. Potrzebuję dalszych wskazówek.

[Premislav]

Zgodnie z sugestią ponumeruj te rzeczy. Skoro wybierasz \(\displaystyle{ 2m+1}\) (czyli nieparzystą liczbę) spośród \(\displaystyle{ n+1}\) rzeczy, to zawsze będzie jakaś rzecz, którą wybierzesz jako \(\displaystyle{ m+1}\). a to oznacza, że przed nią wybrałeś \(\displaystyle{ m}\) (tj. z mniejszymi numerkami) i za nią wybierzesz jeszcze \(\displaystyle{ m}\) rzeczy (za nią, tj. z większymi numerkami), by łącznie było \(\displaystyle{ 2m+1}\). Liczba
\(\displaystyle{ {n-k \choose m} {k \choose m}}\) określa, ile jest takich wyborów, w których środkowa rzecz ma numer \(\displaystyle{ n-k+1, \ k\in\left\{ 0, \ldots n\right\}}\) (tak naprawdę, jak wspomniał już Tmkk, część z tego będzie zerami, niezerowe są współczynniki od \(\displaystyle{ k=m}\) do \(\displaystyle{ k=n-m}\)).