Matematické Fórum

hrubon · 08. 01. 2013 19:26

Zdravím, mám úkol z diskrétky a mám problém. Máme dokázat toto:
${m+n \choose r}=\sum_{i\in [r]}^{}{m \choose i}{n \choose r-i}$
pro $r\le m\le n$ .
Poznámka: $[n]\equiv \{0,1,2,\ldots ,n\}$ , takto to máme definované.

Zvolil jsem indukci podle $r$ :
1.) Indukční předpoklad (IP) (pro: $r=1$ ):
${m+n \choose 1}=\sum_{i=0}^{1}{m \choose i}{n \choose 1-i}$
$m+n=n+m$

2.) Indukční krok (pro $r\ldots r-1$ ):
${m+n \choose r-1}=\sum_{i=0}^{r-1}{m \choose i}{n \choose r-1-i}$
Zde používám indukční předpoklad a nahrazuji sumu levou stranou původní rovnice. Nezapomínám přitom odečíst poslední (r-tý) sčítanec sumy.
${m+n \choose r-1}\stackrel{\text{IP}}{=}{m+n \choose r}-{m \choose r}{n \choose r-r}$
${m+n \choose r-1}={m+n \choose r}-{m \choose r}$
Nyní nastává PROBLÉM. Tahle rovnice prostě neplatí. Zkoušel jsem dosazovat testovací hodnoty $(r=2, m=3, n=4)$ a rovnice nevychází.

Zřejmě jsem něco někde zanedbal nebo předpokládám něco špatně, můžete se na to, prosím, někdo podívat? Díky moc.

check_drummer · 08. 01. 2013 20:49

Ahoj,
nerozumím tomuto kroku:
${m+n \choose r-1}\stackrel{\text{IP}}{=}{m+n \choose r}-{m \choose r}{n \choose r-r}$
Můžeš ho prosím rozepsat? Díky

hrubon · 08. 01. 2013 21:05

↑ check_drummer:
Používám zde indukční předpoklad (proto je nad 'rovná se' napsáno 'IP'). Nahrazuji výraz se sumou levou stranou původní rovnice ze zadání. To mohu udělat, protože předpokládám, že se ta suma rovná levé straně té rovnice (viz. indukční předpoklad). Takže pokud by suma šla do r, byl bych hotov, prostou náhradou pravé strany rovnice za levou. Jenomže suma jde v indukčním kroku do r-1, takže když suma do r je levá strana rovnice, tak od toho ještě musím něco odečíst - a to sice poslední (r-tý sčítanec té sumy). Tak vezmu výraz uvnitř sumy (z původního zadání) a za i dosadím r (protože chci dostat r-tý sčítanec). Čímž dorovnám pravou stranu rovnice a jsem hotov - můžu jít upravovat. Je z toho jasné, jak jsem to myslel?

JohnPeca18 · 08. 01. 2013 22:06

↑ hrubon:
Ani to fungovat nemoze. Ta suma pre r, je trochu jina nez jenom o jeden scitanec delsi.
pre r
${m+n \choose r}=\sum_{i\in [r]}^{}{m \choose i}{n \choose r-i}$

pre r-1
${m+n \choose r-1}=\sum_{i=0}^{r-1}{m \choose i}{n \choose r-1-i}$

v menovateli toho druheho kombinacneho cisla mas r-1, nie r. Ta suma sa neda tak jednoducho rozsirit.

hrubon · 08. 01. 2013 23:15 — Editoval hrubon (08. 01. 2013 23:15)

↑ JohnPeca18:
Díky, chvíli mi to trvalo, ale už tu chybu vidím. Chvilku jsem si s tím (změnil jsem indukci na r...r+1) ${m+n \choose r+1}=\sum_{i=0}^{r}{m \choose i}{n \choose r-i+1}+{m \choose r+1}$
zkoušel hrát a různě vytýkat a upravovat, ale zatím nic z toho nevyšlo tak, abych mohl použít indukční předpoklad. Nenapadá tu někoho, jak by tvrzení dokázal? Nebo z jakého jiného předpokladu vyjít? Díky.

JohnPeca18 · 09. 01. 2013 00:01

A co kdyby si se vykaslal na indukci a dokazal to primo. Leva strana je pocet zpusobu jak vybrat r prvku z m+n prvku a prava strana. Tam vyberes i prvku z m prvku a pak r-i prvku z n prvku, pre ruzne i. Takhle napsany to nezni moc hezky ale podle mne to si staci nejak takhle rozmyslet. Udelat nejaky priklad s kulickama nebo neco takovyho.

Marian · 10. 01. 2013 15:43

↑ hrubon:

Rozviň odle binomické věty výrazy $(1+x)^{m+n}$ , $(1+x)^m$ a $(1+x)^n$ . Využij toho, že platí $(1+x)^{m+n}=(1+x)^m\cdot (1+x)^n$ . Roznásobení pravé strany a porovnáním koeficientů na levé a pravé straně u stejných mocnin $x^i$ dává identitu, která se má dokázat.

hrubon · 11. 01. 2013 10:52

Díky moc,
dřív jsem to odevzdal úvahou s "kuličkama". Ale každopádně díky moc za návod na nějaký formálnější postup, zkusil jsem si to podle něj a hezky to funguje. Ještě jednou díky všem!

Matematické Fórum

#1 08. 01. 2013 19:26

Indukce - špatný předpoklad?

#2 08. 01. 2013 20:49

Re: Indukce - špatný předpoklad?

#3 08. 01. 2013 21:05

Re: Indukce - špatný předpoklad?

#4 08. 01. 2013 22:06

Re: Indukce - špatný předpoklad?

#5 08. 01. 2013 23:15 — Editoval hrubon (08. 01. 2013 23:15)

Re: Indukce - špatný předpoklad?

#6 09. 01. 2013 00:01

Re: Indukce - špatný předpoklad?

#7 10. 01. 2013 15:43

Re: Indukce - špatný předpoklad?

#8 11. 01. 2013 10:52

Re: Indukce - špatný předpoklad?

Zápatí