1-2. óra: A rekurzió és a teljes indukció

A valós sorozatok felderítésérõl szól ez az óra. A valós sorozatok \(a:\mathbb N\rightarrow\mathbb R\) típusú függvények. A függvény valamely \(n\in\mathbb N\) helyen felvett értékét \(a(n)\) helyett inkább \(a_n\)-nel jelöljük, és a sorozat n-edik tagjának nevezzük.

Hogyan lehet egy sorozatot, mint függvényt felderíteni?

Bevezetõ példa: Hanoi tornyai

Mese: Egy tibeti kolostorban a Buddha szobor elõtt három szent rúd áll. Az egyik szélsõn 17 db, közepén lukas szent korong van a rúdra felfûzve, felfele nézve nagyság szerint csökkenõleg. (Ld. ábra!) A szerzeteseknek imádság közben minden nap át kell rakosgatniuk a korongokat a szélsõ oszlopról a másik szélen álló oszlopra, ugyanolyan felfele fogyó méret szerint.

A rakodásnak három fontos (szent) szabálya van:

1. Egyszerre csak egy korong mozgatható
2. Korong csak rúdra rakható. (Földre, vagy más tisztátalan helyre nem.)
3. Nagyobb korong kisebb fölött sohasem állhat.

Kérdés: Elvégezhetõ-e a feladat? Ha igen, hány lépésben? (Egy korong átemelése számít egy lépésnek.)

Elmélkedés...

Mit lehet ezzel kezdeni? Az ember elkezd rakodni, papíron rajzban, vagy szerez valamit amivel ezt manipulatívan is csinálhatja... és ha kitartó, észrevesz ezt azt.

Pl. észreveheti, hogy ha ,,ügyes'', akkor nem fog megakadni, valamiképp mindig lehet folytatni.

Aztán kezdjük a lépéseket számolni. Elég eménytelen (131 071 lépés), ezért ezt józan ésszel feladjuk.

Általánosítsunk!

Nem 17, hanem \(n\in\mathbb N\) db korong helyezendõ át a feltételek szerint. Néha az általános feladat könnyebb, mint a speciális!

\(n=0\)-ra a feladat megoldható 0 lépésben. Ha nincs ilyen matematikus vénánk, akkor...

\(n=1\) koronggal kezdjük, 1 koronggal 1 lépésben oldható meg a feladat. 2 koronggal 3 lépésben, 3 koronggal 7 lépésben.

Kéne találnunk valami rendszert.

1. Észrevétel: (Erre hamar rá lehet jönni.) Az \((n+1)\)-edik koronghoz csak akkor nyúlhatunk hozzá, ha a felette álló \(n\) db-ot tisztán egy oszlopra átraktuk. Ha nem, akkor ugyanis az \((n+1)\)-edik korong még nem szabad, illetve ha szabad is, nem lenne hova tenni.

2. Észrevétel: (Kis számolgatás után adódik ez.) Ha \(n\) db korongot át tudunk valahány lépésben tenni, akkor \((n+1)\)-et is; oly módon, hogy áttesszük az \(n\) db-ot a középsõ oszlopra, majd áttesszük az \((n+1)\)-ediket a kívánt szélsõ oszlopra, végül rápakoljuk az \(n\) db-ot a középsõrõl.

Kiszámolható-e a fenti rekurzió alapján a feladat kérdése? (Hozzávéve még azt, hogy \(H_0=0\).)

Igen.

\begin{equation}
\begin{split}
H_0 &= 0\\
H_1 &= 2\cdot H_0 + 1 = 2\cdot 0 + 1 = 1\\
H_2 &= 2\cdot H_1 + 1 = 2\cdot 1 + 1 = 3\\
H_3 &= 2\cdot H_2 + 1 = 2\cdot 3 + 1 = 7\\
H_4 &= 2\cdot H_3 + 1 = 2\cdot 7 + 1 = 15\\
H_5 &= 2\cdot H_4 + 1 = 2\cdot 15 + 1 = 31\\
H_6 &= 2\cdot H_5 + 1 = 2\cdot 31 + 1 = 63\\
&...
\end{split}
\end{equation}Nos ez elég hosszadalmas. (Mondhatni unalmas.) Persze \(H_{17}\), vagy ha kell \(H_{100}\) is meghatározható, de a dolog egyre hosszadalmasabb.

A rekurzió az elsõ lépés, a sorozat felderítésében, de sokkal "jobb", ha zárt képletet tudunk adni.

Keressük meg a sorozat képletét!

Erõsen "szugerálva" a \(H_n\) sorozat ismert tagjait: 0, 1, 3, 7, 15, 31, 63, ...,  megsejthetõ egy képlet:\[H_n=2^n-1\]Legálábbis így tûnik.

De hogyan lehetne egy ilyet bizonyítani?

Az bizonyos, hogy kis egészekre, pl. \(n=0\)-ra közvetlenül ellenõrizhetõ. De hogyn kezeljük általánosan?

A teljes indukció

Egy speciális, csak a természetes számok halmazán alkalmazható bizonyítási eljárás. Két lépésbõl áll:

1. lépés: Megmutatjuk, hogy az állítás \(n=0\)-ra igaz.
   (Vagy a szóba jöhetõ legkisebb egészre. Ha pl. csak 2-tõl kezdõdõdõen állítunk valamit, akkor \(n=2\)-re igazolunk itt.)
2. lépés (indukciós lépés): Megmutatjuk, hogy ha \(k\in\mathbb N\) egy olyan szám, amire az állítás igaz, akkor \((k+1)\) is olyan (amire az állítás igaz). Ezzel a bizonyítás kész.

Miért bizonyító erejû a teljes indukció?

Egy szemléletes magyarázat a következõ:
\(n=0\)-ra az állítás igaz, de beláttuk, hogy ha valamire igaz, akkor a nála eggyel nagyobbra is, így 1-re is igaz...
... de mivel beláttuk, hogy ha valamire igaz, akkor az eggyel nagyobbra is, így igaz 2-re is...
... de mivel beláttuk, hogy ha valamire igaz, akkor az eggyel nagyobbra is, így igaz 3-ra is...
... stb.

Mivel így bármely természetes számig eljuthatunk, az állítás igaz minden konkrét \(n\)-re. \((n\in\mathbb N)\).

Olyan ez, mint amikor dominókat állítunk sorba, és az elsõt eldöntjük. Mi kell ahhoz, hogy mind eldõljön? Két dolog. 1. az elsõt meg kell lökjük, és 2. biztosak kell lennünk abban, hogy minden dominó felborítja a következõt.

Használjuk a most tanult eljárást!

Állítás: Ha \(H_n\) sorozatot a
\begin{equation}
\begin{split}
H_0 &= 0\text{ ,  ez a kezdõtag}\\
H_{n+1} &= 2\cdot H_n + 1\text{ ,  ez a rekurzió}
\end{split}
\end{equation}definiál, akkor\[H_n=2^n-1 \text{ , }\forall n\in\mathbb N\text{ , esetén}\]

Bizonyítás teljes indukcióval.

1. lépés: \(H_0\). A bizonyítandó képlet szerint \(2^0-1=1-1=0\) Ez rendben van. (\(H_0\)-ra a képlet helyes eredményt ad.)

2. (indukciós) lépés: Legyen \(k\in\mathbb N\) olyan, amelyre az állítás igaz, vagyis\[H_k=2^k-1\]Igazoljuk, hogy akkor \((k+1)\) is ilyen.
\[
\underbrace{H_{k+1}=2\cdot \color{darkgreen}{H_k} +1}_{\text{A rekurzió szerint}} = 2\cdot \left(\color{darkgreen}{2^k-1}\right)+1=2\cdot 2^k-2+1=2^{k+1}-1
\]
Tehát, ha a képlet jó \(k\)-ra, akkor \((k+1)\)-re is jó. Ezzel a bizonyítást befejeztük.

Válasz az eredeti feladatra: A 17 korongot \(H_{17}=2^{17}-1=\) 131 072 - 1 = 131 071 lépésben lehet áthelyezni.