Matematické Fórum

veadet · 24. 09. 2015 22:19 — Editoval veadet (24. 09. 2015 22:22)

Ahojte, potreboval by som trosku pomoct s dokazom matematickou indukciou nasledujucej rovnosti: $\frac{{k \choose 0}}{2^k}+\frac{{k \choose 1}}{2^k} +...+ \frac{{k \choose k}}{2^k}=1$
alebo tiez $\sum_{i=0}^{k}\frac{{k \choose i}}{2^k}=1$
Vedel by mi niekto pomoct?

teolog · 24. 09. 2015 23:25 — Editoval teolog (24. 09. 2015 23:28)

↑ veadet:
Zdravím,
stačí si všimnout, že čitatel vyjadřuje počet všech podmnožin množiny o k prvcích, což je $\mathrm{2}^{k}$ .

Třeba tady je to trochu ukázáno (příklad 6).

EDIT: Tím jsem ale obešel matematickou indukci. Je nutné to mat. indukcí řešit?

veadet · 24. 09. 2015 23:41

Ano, ide o to zostavit dokaz matematickou indukciou. Nie som si isty ako na to. Priamy dokaz urobit viem.

Xellos · 24. 09. 2015 23:51

Dokazujes $\sum_{j=0}^k{k\choose j}=2^k$ .

Pre $k=0$ to plati. Nech to plati pre $k$ , potom vyuzitim vzorca ${k\choose j}={k-1\choose j-1}+{k-1\choose j}$ (plati pre vsetky cele $j$ ak zavedieme ${k\choose j}=0$ pre $j < 0$ alebo $j > k$ )

$\sum_{j=0}^{k+1}{k+1\choose j}=\sum_{j=0}^{k+1}{k\choose j-1}+\sum_{j=0}^{k+1}{k\choose j}=\sum_{j=1}^{k+1}{k\choose j-1}+\sum_{j=0}^{k}{k\choose j}=\sum_{j=0}^{k}{k\choose j}+2^k=2\cdot2^k=2^{k+1}$

teda to plati aj pre $k+1$ a teda indukciou pre vsetky $k$ .

veadet · 25. 09. 2015 10:24 — Editoval veadet (25. 09. 2015 10:33)

Preco dokazujeme $\sum_{j=0}^k{k\choose j}=2^k$ ? ak zavedieme ${k\choose j}=0$ pre $j < 0$ ? $j$ moze byt mensie ako nula?

Rumburak

↑ veadet:

Ahoj.

Rovnosti

(1) $\frac{{k \choose 0}}{2^k}+\frac{{k \choose 1}}{2^k} +...+ \frac{{k \choose k}}{2^k}=1$ ,

(2) $\sum_{j=0}^k{k\choose j}=2^k$

jsou spolu ekvivalentní (když první rovnost vynásobime nenulovým výrazem $2^k$ , dostaneme druhou).

Rovnost (2) je zvláštním případem binomické věty pro $(1 + 1)^k$ , takže když by sis s důkazem ani po dlouhém bádání
nevěděl rady, můžež si najít v učebnici důkaz b.v. pro obecný případ a inspirovat se jím. Ale kolega ↑ Xellos:
Ti už důkaz napsal.

Sčítací index $j$ v symbolu $\sum_{j=0}^k$ probíhá pouze hodnoty $0, 1, ..., k$ , takže záporný být nemůže.

Xellos · 25. 09. 2015 11:36

↑ veadet:
Preco by nemohlo v binomickych koeficientoch $j$ byt mensie ako 0? Ked $k\choose j$ popisuje pocet sposobov ako vybrat $j$ veci z $k$ , tak zaporny pocet veci vybrat nedokazeme, takze pocet sposobov pre zaporne $j$ je 0 :D

Mas aj alternativy ak sa obmedzis na $j \ge 0$ , ale potom ${k\choose j}={k-1\choose j-1}+{k-1\choose j}$ plati len pre $j > 0$ a musis oddelene riesit clen s $j=0$ . Pripadne sa mozes obmedzit na $j \le k$ , a vtedy musis oddelene riesit aj clen s $j=k$ . Moja verzia nema ziadne specialne pripady.

veadet · 25. 09. 2015 11:45

Myslim ze uz rozumiem. Tak Vam obom dakujem za pomoc. :)

vanok · 25. 09. 2015 11:56

Ahoj ↑ veadet:,
Iny dokaz (binomicka rovnost)
$2^k=(1+1)^k=.......$

veadet · 25. 09. 2015 15:13

a v tom medzi kroku $\sum_{j=0}^{k+1}{k\choose j-1}+\sum_{j=0}^{k+1}{k\choose j}=\sum_{j=1}^{k+1}{k\choose j-1}+\sum_{j=0}^{k}{k\choose j}$
to akoze $\sum_{j=0}^{k+1}{k\choose j}=\sum_{j=0}^{k}{k\choose j}$ ??

Xellos · 25. 09. 2015 18:02

↑ veadet:

Kolko je $k \choose k+1$ ?

veadet · 26. 09. 2015 14:25 — Editoval veadet (26. 09. 2015 14:27)

myslim ze $k$

Xellos · 26. 09. 2015 15:32

↑ veadet:

Myslis zle. (Kolkymi sposobmi vies vybrat $k+1$ veci z $k$ ?)

Najprv sa nauc robit s kombinacnymi cislami, az potom mozes s nimi daco dokazovat.

Matematické Fórum

#1 24. 09. 2015 22:19 — Editoval veadet (24. 09. 2015 22:22)

Dokaz vety indukciou

#2 24. 09. 2015 23:25 — Editoval teolog (24. 09. 2015 23:28)

Re: Dokaz vety indukciou

#3 24. 09. 2015 23:41

Re: Dokaz vety indukciou

#4 24. 09. 2015 23:51

Re: Dokaz vety indukciou

#5 25. 09. 2015 10:24 — Editoval veadet (25. 09. 2015 10:33)

Re: Dokaz vety indukciou

#6 25. 09. 2015 11:02 — Editoval Rumburak (25. 09. 2015 11:05)

Re: Dokaz vety indukciou

#7 25. 09. 2015 11:36

Re: Dokaz vety indukciou

#8 25. 09. 2015 11:45

Re: Dokaz vety indukciou

#9 25. 09. 2015 11:56

Re: Dokaz vety indukciou

#10 25. 09. 2015 15:13

Re: Dokaz vety indukciou

#11 25. 09. 2015 18:02

Re: Dokaz vety indukciou

#12 26. 09. 2015 14:25 — Editoval veadet (26. 09. 2015 14:27)

Re: Dokaz vety indukciou

#13 26. 09. 2015 15:32

Re: Dokaz vety indukciou

Zápatí