Matematické Fórum

teolog · 08. 03. 2010 16:08

Zdravím všechny. Chtěl bych poprosit o pomoc s následujícím příkladem:
Dokažte, že pro všechna přirozená čísla n a k splňující $k\leq n$ platí:
${n \choose k}=\sum_{t=1}^{n-k+1} {n-t \choose k-1}$

musixx · 08. 03. 2010 16:35

Matematická indukce spolu se známým (třeba z Pascalova trojúhelníka): ${n\choose k}={n-1\choose k}+{n-1\choose k-1}$ .

teolog · 08. 03. 2010 21:46

↑ musixx:
Díky za nakopnutí, ale pořád nějak tápu.
Můj pokus:
1.Dokázat, že to platí pro k=1 a n=1. Není potřeba rozepisovat.
2.Dokázat, že to platí pro k+1 a n+1:
${n+1 \choose k+1}=\sum_{t=1}^{n-k+1}{{n+1-t \choose k}}$
po úpravě levé strany
${n \choose k}+{n \choose k+1}=\sum_{t=1}^{n-k+1}{{n+1-t \choose k}}$
pak jsem zkoušel toto:
${n \choose k+1}=\sum_{t=1}^{n-k+1}{{n+1-t \choose k}}-\sum_{t=1}^{n-k+1}{{n-t \choose k-1}}$
ale dál už moc nevím. Navíc jsem si teď při přepisování do TeXu uvědomil, že při důkazu požívám to, co dokazuji. Což nelze.
Můžete mi ještě trochu napovědět, jak dál?

lukaszh · 08. 03. 2010 23:01

Indukciu urobíme pre $n\in\mathbb{N}$ . Číslo $1\le k\le n$ je pevne zvolené ľubovoľné. Na to sa indukcia nevzťahuje. Množina prirodzených čísel je nekonečná a nikdy nevieme, či niečo nevyskočí. S číslom k budeme zaobchádzať všeobecne. Predpokladáme teda platnosť
${n\choose k}=\sum_{t=1}^{n-k+1} {n-t \choose k-1}$
Ukazujeme pre n+1 a pevne zvolené k:

Čo je opäť identita známa napríklad z Pascalovho trojuholníka. Korektne by sa to malo robiť "pospiatky" aby šlo o dôkaz. Mne sa to však zdá zbytočné prepisovanie, aj tak každý to urobí najprv takto.

Pavel Brožek · 09. 03. 2010 00:35

Když to zapíšeš takhle, tak není žádný problém s tím, že bys to správně měl dělat od konce.

Já bych to ale stejně asi dělal bez indukce, mnohonásobným použitím vzorce, který navrhoval musixx.

${n\choose k}={n-1\choose k-1}+{n-1\choose k}={n-1\choose k-1}+{n-2\choose k-1}+{n-2\choose k}=\nl ={n-1\choose k-1}+{n-2\choose k-1}+{n-3\choose k-1}+{n-3\choose k}=\ldots=\nl ={n-1\choose k-1}+{n-2\choose k-1}+\ldots+{k\choose k-1}+{k\choose k}=\nl ={n-1\choose k-1}+{n-2\choose k-1}+\ldots+{k\choose k-1}+{k-1\choose k-1}=\nl =\sum_{t=1}^{n-k+1} {n-t \choose k-1}$

teolog · 09. 03. 2010 11:10

Všem díky za snahu. Jen bych se ještě optal. Lukaszh ve svém postupu na začátku předpokládá platnost dokazovaného vzorce a během postupu tento vzorec použije. Ale nejsem si jistý, jestli může v důkazu něčeho to něco použít.

Jinak v té indukci jsem měl trochu zmatek, zda dokazuji jen pro n+1 nebo i k+1, takze lukaszh mi to ujasnil.
A také díky BrozkoviP, jeho postup mi přijde elegantní.

jarrro · 10. 03. 2010 16:51

o tom je indukcia,že predpokladáme pre nejaké n že dokazované platí a snažíme sa z toho dostať,že to platí aj pre prirodzené číslo o jedna väčšie potom z platnosti pre n=1 vyplýva platnosť pre n=2 stade pre n=3 atď

Matematické Fórum

#1 08. 03. 2010 16:08

Důkaz, součet kombinačních čísel

#2 08. 03. 2010 16:35

Re: Důkaz, součet kombinačních čísel

#3 08. 03. 2010 21:46

Re: Důkaz, součet kombinačních čísel

#4 08. 03. 2010 23:01

Re: Důkaz, součet kombinačních čísel

#5 09. 03. 2010 00:35

Re: Důkaz, součet kombinačních čísel

#6 09. 03. 2010 11:10

Re: Důkaz, součet kombinačních čísel

#7 10. 03. 2010 16:51

Re: Důkaz, součet kombinačních čísel

Zápatí