Matematické Fórum

slender · 25. 11. 2015 18:26

Zdravím,
řeším právě úlohu, ve které mám výpočtem nebo kombinatorickou interpretací dokázat následující tvrzení:

${r \choose r} + {r+1 \choose r} + ... +{n \choose r} = {n+1 \choose r+1}$

Chtěl jsem to dokázat indukcí, ale moc daleko jsem se nedostal, nejsem si ani jistý, zda by to fungovalo. (Nenapadá mě, jak vůbec hledat spojitost mezi levou a pravou stranou.)

Pokud mě někdo popostrčíte správným směrem, budu velmi vděčný.

Sherlock · 25. 11. 2015 18:41

Nešlo by dokazovat to s pomocí definice kombinačního čísla? ${n \choose k}=\frac{n!}{k!(n-k)!}$

zdenek1 · 25. 11. 2015 20:02

↑ slender:
pro $n=r$ máš ${r\choose r}={r+1\choose r+1}$ , což triviálně platí

nechť vztah platí pro $n$ , dokazujeme
${r\choose r}+{r+1\choose r}+\dots+{n\choose r}+{n+1\choose r}={n+2\choose r+1}$

$\underbrace{{r\choose r}+{r+1\choose r}+\dots+{n\choose r}}_{{n+1}\choose r+1}+{n+1\choose r}={n+1\choose r+1}+{n+1\choose r}$ a to je obecně známý vztah ${n\choose k}+{n\choose k+1}={n+1\choose k+1}$

slender · 25. 11. 2015 21:38

↑ zdenek1:

Díky moc. Nečekal jsem, že je řešení takhle nasnadě. :)

Matematické Fórum

#1 25. 11. 2015 18:26

Suma kombinačního čísla (důkaz výpočtem nebo kombinatoricky)

#2 25. 11. 2015 18:41

Re: Suma kombinačního čísla (důkaz výpočtem nebo kombinatoricky)

#3 25. 11. 2015 20:02

Re: Suma kombinačního čísla (důkaz výpočtem nebo kombinatoricky)

#4 25. 11. 2015 21:38

Re: Suma kombinačního čísla (důkaz výpočtem nebo kombinatoricky)

Zápatí