Hogyan kell teljes indukcióval bizonyítani?

Teljes indukcióval mindent ugyanúgy kell bebizonyítani, meglehetősen mechanikus a dolog.

1. Megnézed konkrét kis n-re, pl 0-ra 1-re.

2. Felteszed, hogy n-ra igaz.

3. Felhasználva, hogy n-re igaz, belátod, hogy n+1-re is igaz, így a teljes indukció elve miatt, minden természetes számra igaz lesz (az adott első helyes kezdőértéktől).

A teljes indukció lényege, hogy a végtelen sok állítást sorrendben bizonyítod (itt a sorrend: n=1,2,3,...). Attól lesz ez egy erős eszköz, hogy minden egyes esetnél felhasználhatod a korábban bizonyított állításokat is. Pl. ha a fenti sorrendben bizonyítasz, akkor az n=1000 eset bizonyításához felhasználhatod az n=1,2,...,999 esetek mindegyikét. Ezzel persze önmagában nem jó, mert ugyanúgy egyenként bizonyíthatnánk, n=1000, n=1001, stb... Ezért azt csináljuk, hogy n legyen paraméter, és TETSZŐLEGES n-re leírjuk a bizonyítást - azaz minden n-re egyszerre. Például indukcióval, így: tegyük fel, hogy az n=k-1 esetet beláttuk. Most igazoljuk az állítást n=k-ra. Tehát az n=1,2,...,(k-1)-re már bizonyított az állítás, és ezt fel is használhatjuk az n=k eset bizonyításához.

És most jöjjön végre a feladat: n=1,2,...-re F(n)=2^(6n+1)+3^(2n+2) osztható 11-gyel. Két eset legyen:

1. eset: n=1, ekkor igaz, mert F(n)=209=11*19.

2. eset: n>1, ekkor az indukciós hipotézis értelmében F(n-1) osztható 11-gyel, ezt a segítséget használjuk fel.

Nos, itt többféleképp eljárhatunk, de F(n)-et valahogy úgy kell átalakítani, hogy hivatkozzunk F(n-1)-re. Vagyis bele kell varázsolni valahogy F(n-1)-et F(n) kifejtésébe. Erre egy lehetséges módszer: F(n-1) = 2^(6(n-1)+1) + 3^(2(n-1)+2), tehát 3^(2n) = F(n-1) - 2^(6n-5), ezt felszorozva 3^2-nel (9-cel): 3^(2n+2) = 9*F(n-1) - 9*2^(6n-5). Ez arra jó, mert F(n) kifejtésében szerepel 3^(2n+2), tehát behelyettesíthetünk:

F(n) = 2^(6n+1) + 3^(2n+2) = 2^(6n+1) + 9*F(n-1) - 9*2^(6n-5) = 9*F(n-1) + 2^(6n-5)*(2^6-9) = 9*F(n-1) + 2^(6n-5)*55.

És kész a bizonyítás, mert mindkét tag osztható 11-gyel (az egyikben az F(n-1), a másikban az 55 tényező miatt).

Megjegyzések.

- Az indukció iskolás példáinál leggyakrabban elégséges csak az "előző" állítást felhasználni: vagyis n=k bizonyításához csak azt, hogy n=k-1-re igaz a tétel. Ez a megoldás is csak ezt használta, de valójában használható lett volna az összes korábbi eset, mindegyike (csak így most ez elég).

- Az esetszétválasztás (n=1 és n>1) azért kell, mert az n=1 eset a legelső, nincs hozzá képest megelőző állítás (n-1=0), amit fel lehetne használni - nincs más mód, ezt az egy esetet külön kell bizonyítani. Nem nehéz, de tanárok harapnak érte, ha elmarad. Ez a kezdeti eset az indukció kezdő feltétele, szinte mindenhol külön kell kezelni.

- Ez egy GAGYI feladat az indukció témakörhöz, mert ezt tipikusan nem azzal kell megoldani. Lényegesen egyszerűbb megoldás (precíz indoklás nélkül):

2^(6n+1) + 3^(2n+2) = 2*64^n + 9*9^n. Mivel 11-es maradékot nézel, minden tényezőt helyettesíthetsz a 11-es maradékával (ez egy nagyon hasznos alapelv), vagyis a 64-ek helyébe 9-et, hiszen 2*64^n valójában egy szorzat: 2*64*64*...*64 -> 2*9*...*9. Így az eredeti kifejezés átalakítottja most már így néz ki: 2*9^n + 9*9^n = 11*(9^n) - tadam, és még a pontos értékét is kiszámoltuk.

n=0-ra:

2^1+3^2=11 ez tényleg osztható 11-el.

Indukciós feltevés:

2^(6n+1) + 3^(2n+2) osztható 11-el.

Lássuk be, hogy n+1-re is igaz, vagyis n helyére n+1-et kell írni:

2^(6(n+1)+1) + 3^(2(n+1)+2)

2^(6n+1+6) + 3^(2n+2+2)=2^6*2^(6n+1)+3^2*3^(2n+2)=

64*2^(6n+1) + 9*3^(2n+2)

Erről kell belátni, hogy osztható 11-el, méghozzá az indukciós feltevés segítségével.

64=55+9

55*2^(6n+1)+9*2^(6n+1) + 9*3^(2n+2) =

55*2^(6n+1)+9*[2^(6n+1) + 3^(2n+2)]

Az első tag osztható 11-el, mert 55 = 5*11

A 2. tag meg az indukciós feltevés miatt osztható.

Ezzel beláttuk, hogy a kifejezés osztható 11-el, és készen vagyunk.

A szép hosszú #2-es válaszból csak a lényeg maradt ki.

A teljes indukció bizonyos szabályoknak egy speciális bizonyítási technikája. A szabályok bizonyos elemek halmazára fognak vonatkozni. Ezeket az elemeket először is sorba kell tudnunk rakni (az a bizonyos "n" azt jelenti, hogy az n-dik elemről beszélünk, de az elem maga bármi lehet). Ezután kidolgozunk egy olyan általános algoritmust, amelyben, ha feltételezzük egy elemről, hogy a szabály igaz rá, akkor a következőre szintén igaznak kell lennie. Az első elemről valamilyen módon bebizonyítjuk, hogy igaz rá a szabály (például nyilvánvaló mindenki számára). Ezzel készen is vagyunk, mert a másodikra igaz, hiszen azt megmutattuk, hogy a következőre teljesül, ha az előzőre igaz.

Egy elemre azért kell külön megmutatni, hogy a szabály érvényes rá, mert a bizonyításunk lényege, hogy tudjuk folytatni. De ha nem lenne kezdet, folytatás sincs.

A konkrét példa: n=0 esetén 2^1+3^2=11 ez osztható önmagával, vagyis a szabály n=0-ra igaz.

Jelöljük n esetén az első hatványt "A"-val, a másodikat "B"-vel.Ha n-re igaz, akkor n+1 esetén a szám 2^(6n+7)+3^(2n+4)=2^(6n+1)*2^6+3^(2n+2)*3^2=64*A+9*B.

Mivel A+B osztható 11-gyel, így a kilencszeresük is. És ha két szám osztható 11-gyel, akkor a különbségük is. Tehát 64*A+9*B-9*(A+B)=55*A=11*5*A. Ez a szám is osztható 11-gyel. Beláttuk tehát, hogy ha a szám n esetén osztható 11-gyel, akkor n+1 esetén is. Mivel n=0-ra igaz volt, ebből következik, hogy n=1-re is, abból meg hogy n=2-re, és így tovább. Ezzel beláttuk, hogy minden n-re igaz. Ha ugyanis nem lenne igaz, akkor az előzőre se, az azelőttire se, végig, majd a nullára se. Márpedig arra igaz. Vagyis ha nem teljesülne, az nyilvánvaló ellentmondáshoz vezetne.