Matematické Fórum

Mirgeee · 22. 09. 2013 19:37

Ahoj, prosím o pomoc s touto úlohou: Dokažte, že pro n-té prvočíslo p(n) platí p(n+1) <= p(1)*p(2)*...*p(n)+1. Mělo by se to dokazovat pomocí indukce.

Formol · 23. 09. 2013 07:48

↑ Mirgeee:
Dovolím si jen malou nápovědu - zkus se podívat na důkaz, že je prvočísel nekonečně mnoho. Mělo by tě to inspirovat;-)

Mirgeee · 23. 09. 2013 09:53

Díky. Ten já znám, ale zdá se mi, že pokud na ten důkaz půjdu tímto způsobem (tedy podle mě využitím faktu, že ta pravá strana musí být dělitelná nějakým prvočíslem větším než p(n), nemusím užít indukce. Nebo se pletu?

Brano · 23. 09. 2013 14:16 — Editoval Brano (23. 09. 2013 14:29)

↑ Mirgeee:
mas pravdu - nemusis ju v tej technike pouzit. ale kedze ziaden elegantny dokaz vyuzivajuci indukciu ma nenapada, tak mozes tento rozsirit na dokaz indukciou, tak ze tam pridas dve zbytocne vety:

1) $p(2)=3\le 2+1=p(1)+1$
2) Predpokladajme, ze $p(n)\le p(1)..p(n-1)+1$ a chceme dokazat, ze $p(n+1)\le p(1)..p(n)+1$ .
A potom to dokazes bez vyuzitia toho predpokladu, ale to formalne vobec nevadi.

EDIT: tak ma este napadlo, ze ta indukcia by tam mala zmysel, keby si este akoze ani nemala vetu, ze prvocisel je nekonecne vela a teda ani to, ze z nich mozes vyrobit postupnost. A potom by si chcela dokazat nieco v tomto duchu:
Dokazte, ze existuje postupnost $p(n)$ splnajuca $p(n)<p(n+1)\le p(1)\cdot...\cdot p(n)+1$ a prebiehajuca cez vsetky prvocisla.
Potom by sa teda ta indukcia pekne pouzila na zrozumitelnu konstrukciu tej postupnosti.

Formol · 23. 09. 2013 14:52 — Editoval Formol (23. 09. 2013 14:55)

Omlouvám se, ale přivedl jsem tě tak trochu na zcestí, protože se mi na první pohled zdálo, že využiješ toho, že na pravé straně máš prvočíslo.

Nejprve předpoklad: Např. pro n=2 to platí, protože 7<=2*3+1=7

Dále indukční krok. Tady jde použít Cimrmanův krok stranou, protože konstrukce vyššího prvočísla z důkazu nekonečného počtu ti nezaručuje, že jde o nejbližší vyšší prvočíslo. Zaručuje ti ovšem, že jde o horní závoru; tedy když to pro n prvočísel platí, lze analogicky vytvořit horní závoru i pro n+1 prvočísel. Tedy platí-li vztah pro n, platí i pro n+1.

Ono se může zdát, že jde o něco samoúčelného a že v tom indukce není nutná, protože "je to vidět". To je ale omyl, ty chceš ukázat, že to pro všechna n platí, takže musíš postupovat induktivně. Až se později dostaneš ke složitějším konstrukcím, tak zjistíš, že u řady důkazů zajímavých vět je nejprve třeba ukázat, že vůbec existují objekty, o kterých dané tvrzení něco vypovídá - a na to jsou takovéhle "zbytečné komplikace" celkem dobrou přípravou.

EDIT: Omlouvám se za duplicitní odpověď, vytvářel jsem ji v průběhu pracovního procesu, takže jsem přehlédl, že Brano odpověděl dříve a lépe.