Dowody kombinatoryczne tożsamości

[karaoke120]

Udowodnij kombinatorycznie następującą tożsamość \(\displaystyle{ \sum_{k=0}^{m} {n+k \choose k} = {n+m+1 \choose m}}\)

[robsel]

1 sposób: indukcja ze względu na \(\displaystyle{ n}\)
2. tzw. dowód kombinatoryczny, polegający na ułożeniu odpowiedniej 'historyjki'

[karaoke120]

Interesuje mnie to drugie. Prawa strona jest liczbą danych podzbiorów, nie wiem jednak jak opisać stronę lewą, żeby ta równoliczność była widoczna.