Matematické Fórum

alfacentauri · 09. 12. 2014 15:35

Ahoj,
mám triviální problém. Mám dokázat, že $\binom{2n}{n}$ je dělitelné 4-mi, kromě n = mocnina dvou.
Tzn. že musím dokázat, že v čitateli bude v prvočíselném rozkladu o 2 dvojky více než ve jmenovateli. A proč v mocninách 2 je v čitateli jen o 1 dvojku více.
Určitě to jde nějak triviálně dokázat. Třeba jenom z rozepsání:
$\binom{2n}{n}=\frac{2n(2n-1)(2n-2)...n(n-1)(n-2)...\cdot 2\cdot 1}{n(n-1)(n-2)...\cdot 2\cdot 1\cdot n(n-1)(n-2)...\cdot 2\cdot 1 }=\frac{2n(2n-1)(2n-2)...(n+1)}{n(n-1)(n-2)...\cdot 2}$
Díky

Eratosthenes · 09. 12. 2014 17:37

ahoj ↑ alfacentauri:,

Jednu dvojku navíc už tam máš (tu první). A co toto: (2n-2)=2*(n-1)? - druhá závorka v čitateli :-)

alfacentauri · 09. 12. 2014 18:19

Díky za příspěvek. Ta první dvojka moc použít nejde protože se vykrátí s posledním členem jmenovatele. To vytknutí mě ve skutečnosti už to napadlo, ale nějak jsem to nebral za důležité. Teď ale přemýšlím, že by šli ty členy rozdělit do skupinek a něco s tím možná udělat... Něco ukusím

Brano · 09. 12. 2014 18:51

urcite sa to da robit vselijak, ale mna napadla takato srandicka

oznacme si $f(n)=\max\{k;2^k|n!\}$ potom si dokaz, ze $f(n)=\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{n}{4}\right\rfloor+\left\lfloor\frac{n}{8}\right\rfloor+...+\left\lfloor\frac{n}{2^k}\right\rfloor$ kde $k=\lfloor\log_2(n)\rfloor$
a teba vlastne zaujima
$f(2n)-2f(n)=n-f(n)=n-\left(\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{n}{4}\right\rfloor+\left\lfloor\frac{n}{8}\right\rfloor+...+\left\lfloor\frac{n}{2^k}\right\rfloor\right)\ge n-\left(\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+...+\frac{n}{2^k}\right)=\frac{n}{2^k}\ge 1$
a uz sa da lahko overit, ze rovnost nastane prave vtedy ked $n$ je mocnina dvojky.

alfacentauri · 09. 12. 2014 19:17

Už dřív mě napadla podobná věc, ale nedokázal jsem jí dovést do konce. Díky. Podívám se na to.

Eratosthenes · 10. 12. 2014 10:18

ahoj ↑ alfacentauri:,

Pravda, tu poslední dvojku jsem nějak zasklil, omlouvám se. Ale měl by fungovat postup kolegy ↑ Brano:.

vanok · 10. 12. 2014 13:34

Poznamka:
Staci pouzit znamy stredoskolsky vzorec
$p\binom{n}{p}=n\binom{n-1}{p-1}$ .

Brano · 10. 12. 2014 15:28 — Editoval Brano (10. 12. 2014 15:29)

↑ vanok:
vobec mi nie je jasne ako to pomoze, mozes to prosim rozviest?

vanok · 11. 12. 2014 01:07

Ahoj ↑ Brano:,
Mas pravdu, vzorec co som napisal vyssie da lahko delitelnost 2 my, ale nie 4 my.
Zda sa ze problem nie je taky jednoduchy ako sa zda na prvy pohlad.
Toto som nasiel na webe
http://www.primepuzzles.net/problems/prob_043.htm
A na Google pozriet
divisor of central binomial coefficients
divisor of Catalan numbers
Moze dat nieco zaujimave.

Matematické Fórum

#1 09. 12. 2014 15:35

důkaz dělitelnosti

#2 09. 12. 2014 17:37

Re: důkaz dělitelnosti

#3 09. 12. 2014 18:19

Re: důkaz dělitelnosti

#4 09. 12. 2014 18:51

Re: důkaz dělitelnosti

#5 09. 12. 2014 19:17

Re: důkaz dělitelnosti

#6 10. 12. 2014 10:18

Re: důkaz dělitelnosti

#7 10. 12. 2014 13:34

Re: důkaz dělitelnosti

#8 10. 12. 2014 15:28 — Editoval Brano (10. 12. 2014 15:29)

Re: důkaz dělitelnosti

#9 11. 12. 2014 01:07

Re: důkaz dělitelnosti

Zápatí