The Postal Owl

Početně:
Indukcí:
pro $n = r$
$\binom{r}{r} = 1 = \binom{r+1}{r+1}$ Pokud platí pro $n$, dokazme pro $n+1$

$\sum^{n+1}_{k=r} \binom{k}{r} = \sum^{n}_{k=r} \binom{k}{r} + \binom{n+1}{r} = \binom{n+1}{r+1} + \binom{n+1}{r}$

Toto můžeme sečíst

$\sum^{n+1}_{k=r} \binom{k}{r}=\binom{n+2}{r+1}$

Takže tvrzení platí.

Kombinatoricky: Rozložme výběr r+1 z n+1 prvků podle toho, kdo bude první vybraný. Pokud prvního zařadíme do výběru, pak vybíráme zbylých r z n, pokud prvního nevybereme a druhého ano, pak nám bude zbývat vybrat r z n-1. Takhle pokračujeme až dokud nevybereme prvních n-r prvků a pak už musíme vybrat těch zbylých r.