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.

Preview