Matematické Fórum

Sherlock

Zdravím,

Pokud jsem to správně pochopil, mat. indukce se dá formálně zapsat takto (s počátečním n=1):
$(P(n)\wedge P(1))\Rightarrow P(n+1)$

Můžu ale použít mat. indukci třeba i takto?
$(P(1)\wedge P(n)\wedge P(n-1)\wedge P(n-2))\Rightarrow P(n+1)$

nebo takto?
$(P(n-k)\wedge P(k))\Rightarrow P(n+1)$ , $n>k$

Jestli ano, proč? :-)

Xellos · 23. 09. 2015 21:57

Ano, ale v druhom pripade potrebujes pociatocne $P(1..3)$ , nie len $P(1)$ a treti je zbytocna namaha, lebo pre $k=1$ sa zredukuje na prvy. Chytrejsie je napr. indukcia cez mocniny 2: $P(1)$ plati a $P(n)\Rightarrow P(2n)$ .

Indukciu mozes pouzit s lubovolnym krokom a startom. Preco? Funguje to podla mat. logiky (pomocou platnych vyrokov dostavas dalsie platne), preto. Len si musis dat pozor co tym dokazes.

Brano · 23. 09. 2015 22:36 — Editoval Brano (23. 09. 2015 22:36)

zapisujes to dost neporiadne:

standardna matematicka indukcia vyzera takto

Ak $P(0)$ a $\forall_n [P(n)\Rightarrow P(n+1)]$ potom $\forall_n P(n)$

varianta, ktorej sa hovori uplna indukcia vyzera takto

Ak $P(0)$ a $\forall_n [(\forall_{k\le n} P(k))\Rightarrow P(n+1)]$ potom $\forall_n P(n)$

(lahko sa da presvedcit, ze su ekvivalentne)

ak chces ale skakat o viac ako o jedna - napr nieco taketo
$\forall_n [P(n)\Rightarrow P(n+2)]$ tak potrebujes zacat a $P(0)$ aj $P(1)$ - lebo z nuly by si vyrobil iba parne cisla a tak by si en vyrok mal dokazany iba na parnych cislach
- vo vseobecnosti si mozes vymysliet lubovolnu schemu generovania novych cisel, len si musis uvedomit ake cisla vies z danych zaciatocnych podmienok a daneho predpisu potom vygenerovat a to bude obor na ktorom ti bude dany vyrok platit

Sherlock · 24. 09. 2015 17:09

Zdravím, díky, hned je mi to o něco jasnější :)

Měli jsme jeden příklad na tu úplnou mat. indukci:

Součet vnitřních úhlů v konvexním n-úhelníku je $(n-2)\pi$ .

Začneme rozdělením n-úhelníku úhlopříčkou, dostaneme 2 menší x-úhelníky, jeden má $k$ vrcholů a druhý $n-k+2$ .

Je korektní tento postup?
Pro $P(3)$ výrok platí.
Předpokládejme $P(k),P(n-k+2)$ , chceme se dostat k tomu, že platí $P(n)$ (kde $n-1\ge k$ ). Do vzorce dosadíme $k$ a sečteme s vzorcem, do kterého bylo dosazeno $n-k+2$ . Dostaneme vzorec pro $n$ .

vanok · 24. 09. 2015 17:27 — Editoval vanok (24. 09. 2015 18:34)

Ahoj ↑ Sherlock:,
Ak to napises pozorne ako ti poradil Brano nie je s tym problem.
I ked je to trochu zbytocne... ( no formalne ekvivalentne z beznou indukciou )
Dokonca je to dokazatelne aj bez indukcie.

Inac to je chyba ( stedoskolsky zlozvyk) povedat sucet uhlov, ked treba povedat sucet mier uhlov

Brano · 24. 09. 2015 21:25 — Editoval Brano (24. 09. 2015 21:26)

To co si v podstate dokazal je toto

$P(3)$ a $\forall_{a,b\ge 3}P(a)\wedge P(b)\Rightarrow P(a+b-2)$

takze tu nemusis moc spekulovat staci dosadit $a=n$ a $b=3$ a dostanes vyrok

$\forall_{n\ge 3}P(n)\Rightarrow P(n+1)$ - $P(3)$ v tom predpoklade nemusis furt kopirovat, lebo to vies, ze plati.

co je uplne normalna indukcia - a z nej mas $\forall_{n\ge 3}P(n)$

Matematické Fórum

#1 23. 09. 2015 18:01 — Editoval Sherlock (23. 09. 2015 18:04)

Důkaz matematickou indukcí

#2 23. 09. 2015 21:57

Re: Důkaz matematickou indukcí

#3 23. 09. 2015 22:36 — Editoval Brano (23. 09. 2015 22:36)

Re: Důkaz matematickou indukcí

#4 24. 09. 2015 17:09

Re: Důkaz matematickou indukcí

#5 24. 09. 2015 17:27 — Editoval vanok (24. 09. 2015 18:34)

Re: Důkaz matematickou indukcí

#6 24. 09. 2015 21:25 — Editoval Brano (24. 09. 2015 21:26)

Re: Důkaz matematickou indukcí

Zápatí