Tożsamości kombinatoryczne

[Macies]

Udowodnij podane tożsamości kombinatoryczne.
Niestety nie algebraicznie lecz poprzez nadanie odpowiednich interpretacji kombinatorycznych.
Pozostały mi dwie tożsamości, dla których niczego nie mogę wymyślić
1)
\(\displaystyle{ \sum_{k = 0}^{n} \binom{r + k}{k} = \binom{r+n+1}{n}}\)

2)
\(\displaystyle{ \sum_{r = 0}^{n} \binom{r}{k} = \binom{n+1}{k+1}}\)

[janusz47]

1)
Tożsamość jest związana ze zliczaniem na dwa sposoby \(\displaystyle{ n}\) - elementowych podzbiorów \(\displaystyle{ A \subseteq X = \left\{1,2,3,..., r+n+1 \right\}.}\)

Podzbiory te możemy podzielić na grupy rozłączne ze względu na parametr \(\displaystyle{ j, 1\leq j \leq n+1.}\)

Grupa taka zawiera \(\displaystyle{ {r+n+1- j \choose n-(j - 1)}= {r+n+1 - j \choose n - j + 1 }}\) podzbiorów.

Podstawiając \(\displaystyle{ k = n+1-j}\), gdzie \(\displaystyle{ j}\) jest elementem minimalnym podzbioru otrzymujemy żądaną tożsamość.

2)
W podobny sposób tożsamość ta "zlicza" podzbiory \(\displaystyle{ (k+1)}\) - elementowe zbioru

\(\displaystyle{ \left\{ 1,2.3,..., n+1 \right\}}\) ze względu na parametr \(\displaystyle{ r= n+1 -j}\),

gdzie \(\displaystyle{ j}\) jest elementem minimalnym podzbioru.