Matematická indukce v nerovnicích

Ahoj Honzo,

pokud dobře chápu důkaz indukcí, tak bych postupoval takto:

1. Pro číslo 4 tvrzení platí, dokažme to "ještě" pro n>=5
2. Je třeba dokázat, že z předpokladu 2^n >= n^2 plyne 2^(n+1) >= (n+1)^2 tj. 2.2^n >= n^2+2n+1
3. Je zřejmé, že 2.2^n >= 2.n^2
4. Když dokážeme, že 2.n^2 > (n+1)^2, dokážeme i že: 2.2^n > n^2+2n+1, což se dá napsat jako: 2^(n+1)>(n+1)^2, což chceme dokázat.
5. Tedy pro n >= 5 je n-1 >= 4 /Umocním (obě strany jsou kladné)
6. (n-1)^2 > 4^2 > 2
7. n^2-2n+1 > 2 /-2+n^2
8. 2.n^2-2n-1 > n^2 /+2n+1
9. 2.n^2 > n^2+2n+1 = (n+1)^2 (cíl ze 4)
10. QED

Snad uvažuji správně, je to jedna z mých prvních zkušeností s mat. indukcí.

Martin

Není mi jasný úplně 4. krok. Pokud by to z toho plynulo, stačí spočítat nerovici plynoucí z výrazu 2.n^2 > (n+1)^2 ne? Vyšlo by, že pro n > 1 + sqrt(2) tato nerovnost platí, což se shoduje s naší podmínkou n >= 5, nestačilo by to tak? A ještě u 7. a 8. bodu, co jsou ty / ? Nemají tam být nějaké závorky? Díky

EDIT 1: Hlavní otázkou pro mě ale zůstává, proč když dokážeme 2.n^2 > (n+1)^2, dokážeme i že: 2.2^n > n^2+2n+1 ?

EDIT 2: Dobrý, asi tomu rozumím. Pokud platí 2n^2 > (n+1)^2 , tak z toho plyne, že 2^(n+1) >= 2n^2 > (n+1)^2, nacož jsme přišli za použití indukčního předpokladu 2^n >= n^2. Protože jsme z úvodního výrazu dokázali výraz pro 2^(n+1), QED, whatever that means :D

S tou nerovnicí máš asi pravdu, ale asi by bylo třeba, aby to ještě někdo tady potvrdil, protože s těmi důkazy a logikou je to někdy zrádné.

Ano, jde jen o to, že ten předpoklad je, že platí nějaké a > b a chceme dokázat a > c, kde pro b > c to bude jistě platit. To / a to zatím jsou úpravy rovnice, omlouvám se za mystifikaci, jestli to u vás píšete jinak. :-) QED je zkratka z latiny (quod erat demonstrandum), znamenajíc "což mělo být dokázáno" nebo "což bylo dokázati". :-)

Máš to správně, Martine, i když v trochu nešťastném pořadí.

Formálně správný důkaz musí být série navazujících kroků, když skáčeš tam a zpět, komplikuješ si život.

Trochu si to zjednodušíme, platí:

a) n >= 4

b) indukční předpoklad 2^n >= n^2

2^(n+1) >= 2^n + 2^n >= n^2 + n^2 [podle indukčního předpokladu] ...

... >= n^2 + 4*n [protože n >= 4] ...

... >= n^2 + 2n + 2n >= n^2 + 2*n + 8 [protože n >= 4] ...

... >= n^2 + 2*n + 1 = (n+1)^2

Tedy 2^(n+1) >= (n+1)^2, pokud platí indukční předpoklad.

QED [pokud ti to udělá radost :]

Ja to vnimam nejak takto, je to spravne?

Honzo, máš tam takovou nepěknou věc.

Podle zadání je n z množiny přirozených čísel a na přirozených číslech je trochu problém s dělením a odmocninou, pokud vedou na reálná čísla.

Pokud bychom to brali striktně, tak jsi porušil podmínky úlohy.

Navíc ty i Martin skáčete v důkazu mezi myšlenkami a hranice mezi důkazem a analýzou důkazu je poměrně tenká.

V čistém důkazu bys opravdu měl pouze stavět na známých faktech, nikoliv zjišťovat, jestli zpětně platí nějaké podmínky.

EDIT: Podívej se na můj důkaz a zamysli se nad jednotlivými kroky. Nepoužívám tam nic jiného, než podmínky, které jsou stanoveny na začátku.

2^(n+1) >= 2^n + 2^n >= n^2 + n^2 [podle indukčního předpokladu] ...

... >= n^2 + 4*n [protože n >= 4] ...

Moc tady nechapu, kde jsi prisel k tomu 4*n

:-) Jestli ti to řeknu, budeš si připadat jako pitomec, jak je to jednoduché. Takže, opravdu na to nepřijdeš?

Dobrý, už jsem na to přišel. Je nějaké řešení, které by se dalo aplikovat na všechny příklady? Jiné než vymýšlení nějakého triku. Nějaké jednoduché, obecné. Třeba to moje, co jsem navrhnul, ač není asi zcela korektní, jde aplikovat na všechny příklady tohoto typu. Je toho na škole docela hodně, tak bych něco takového zjednodušujícího docela ocenil.

Šikulka :-)

Ohledně tvé otázky tě asi zklamu. Je to hodně let praxe a tuna důkazů, aby to šlo jednoduše a obecně.

Nevím, jak pracujete s důkazy, ale pokud používáte formální přístup, tak si všimni, že většina důkazů začíná tvrzením, pak se vezmou nějaké magické hodnoty buhví odkud, vloží se do výrazu a vypadne z toho dokazovaná věta.

Takové postupy se často musí číst odzadu, aby se dalo pochopit myšlenku.

Pak se z toho stane druhá přirozenost a hodně lidí včetně mě si prochází důkazy z různých zdrojů, abychom pochopili myšlenky postupů, u kterých je snaha o "intuitivní" vysvětlení. Pak zjistíš, že intuitivní vysvětlení je nutně zkomolené, a proto celou dobu nedávalo smysl.

Špatná zpráva je, že tě na škole neučí, že řadu důkazů vymýšlelo mnoho lidí celý život, zatímco vám se to předkládá jako zjevný fakt a člověk se skoro cítí méněcenný, protože "je to prý snadné". Nevěř tomu a nic si z toho nedělej, pokud v tématu plaveš. Mně trvalo skoro 20 let, než si to sedlo a začalo to dávat dokonalý smysl. I přesto řeším řadu problémů, nad kterými sedím týdny, než se dopracuji k výsledku.

Bavil jsem se o tomto s mym ucitelem na analyzu a muj postup se mu zdal byt korektni. Mluvil neco o restrikci, ale nerad bych tu rekl nejakou blbost.