Udowodnij kombinatorycznie

[max123321]

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

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?

[janusz47]

Zliczamy na dwa sposoby \(\displaystyle{ m}\) - elementowe podzbiory \(\displaystyle{ A \subseteq X =\{ 1,..., n+m+1\}.}\)

Podzbiory te możemy podzielić na grupy rozłączne ze względu na parametr \(\displaystyle{ j = min(X\setminus A).}\)

Stąd wynika, że dla każdego \(\displaystyle{ j, \ \ 1\leq j \leq m+1,}\) grupa taka zawiera \(\displaystyle{ {n+m +1-j \choose m-(j-1)} = {n+ (m-j+1)\choose m - j +1}}\) podzbiorów.

Wystarczy teraz dokonać podstawienia \(\displaystyle{ k:= m-j+1,}\) otrzymując żądaną tożsamość kombinatoryczną.