Teljes indukció

A teljes indukció a matematikában gyakran használt bizonyítási módszer, leggyakrabban akkor, ha természetes számokkal vagy valamilyen más sorozattal dolgozunk.

Az elv

Az alapelv az, hogy az adott állítást bebizonyítjuk valamilyen első elemre, a pozitív egész számok között ez leggyakrabban az n = 1. Ezt egyszerű behelyettesítéssel bizonyítjuk. A következő, indukciós lépésben bebizonyítjuk az „ha az állítás igaz n = a-ra, akkor igaz n = a + 1-re is” implikációt.

Ebből a két lépésből levezethetjük, hogy az adott kifejezés minden n-re igaz (valamilyen halmazból, amellyel éppen dolgozunk). Miért van ez így? Az elején bebizonyítjuk, hogy a kifejezés igaz n = 1-re. Egyúttal tudjuk, hogy ha a kifejezés igaz n = a-ra, akkor igaz n = a + 1-re is. Legyen tehát a = 1. Tudjuk, hogy a = 1-re a kifejezés igaz, és azt is tudjuk, hogy igaz a + 1 = 2-re. Ebben a pillanatban tudjuk, hogy a kifejezés igaz a = 2-re. De mivel igaz a + 1-re is, igaznak kell lennie a 2 + 1 = 3-ra is. És így tovább.

Első példa

Az első példa triviális lesz. Bebizonyítjuk, hogy ha bármelyik páros számhoz hozzáadunk kettőt, megint páros számot kapunk. Mivel pozitív egész számok között mozgunk, a páros számot általánosan 2n alakban írjuk fel, ahol n pozitív egész szám. Ha n helyére bármilyen pozitív egész számot behelyettesítünk, az eredmény páros szám lesz, ez első pillantásra látszik. Az oszthatóságot függőleges vonallal jelöljük így:

$$2\mid 2n$$

Ez a jelölés azt jelenti, hogy a kettes maradék nélkül osztja a 2n kifejezést. Ha már fel tudjuk írni az oszthatóságot, felírhatjuk azt is, amit teljes indukcióval be kell bizonyítanunk.

$$2\mid 2n+2;n\in {\mathbb{N}}^{+}$$

Ezt kell az első példában bebizonyítanunk, vagyis hogy a kettes osztja a 2n + 2 kifejezést – ez pontosan megfelel az eredeti szöveges feladatnak: „ha bármelyik páros számhoz hozzáadunk kettőt, megint páros számot kapunk”.

Az indukció első lépésében ezt az első elemre, az egyesre bizonyítjuk. A kifejezésbe behelyettesítjük az n = 1-et:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

A kettes maradék nélkül osztja a négyest, tehát az első elemre ez igaz. Ezután jön az indukciós lépés, amelyben be kell bizonyítanunk, hogy ha ez igaz az a-adik elemre, akkor igaz az (a + 1)-edik elemre is. Az elején feltételezzük, hogy a feltevésünk igaz, vagyis n = a:

$$2\mid 2a+2$$

Erről a kifejezésről feltételezzük, hogy igaz – a bizonyítás megszerkesztésekor felhasználjuk. Most azt akarjuk bebizonyítani, hogy

$$2\mid 2(a+1)+2.$$

Mit csináltunk? Az a helyére az (a + 1)-et írtuk. A zárójelek fontosak, ez a kifejezés rossz lenne: 2a + 1 + 2. Nem az egész kifejezéshez adunk egyet, hanem az a-ból csinálunk eggyel nagyobb kifejezést, vagyis (a + 1)-et. A kifejezést a zárójel felbontásával alakítjuk át.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Most egy kis kitérő az oszthatósághoz. Ha van két számunk, mondjuk p és q, amelyek oszthatók valamilyen számmal, mondjuk r-rel, akkor igaz, hogy az összegük is osztható r-rel. Tehát igaz:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Behelyettesíthetjük például a p = 8, q = 20 és r = 4 számokat. Látjuk, hogy a négyes osztja a nyolcast is, a huszast is. És ugyanígy osztja az összegüket is, a 8 + 20 = 28-at.

Hogyan használjuk ezt ki a példánkban? A jobb oldalt felbontjuk a p és q számokra így:

$$p=2a+2;q=2$$

A q szám, vagyis a kettes, triviálisan osztható kettővel. A p kifejezés is osztható kettővel, mert ezt mondja a feltevés. A p kifejezés pontosan megfelel a feltevésünknek, amelyről feltételezzük, hogy igaz. És ha a p osztható kettővel, és a q is osztható kettővel, akkor az összegük is osztható kettővel.

Még egyszer a feltevésről. Az elején azt mondtuk, hogy feltételezzük, hogy igaz

$$2\mid 2a+2.$$

Ezért amikor a bizonyítás megszerkesztése közben belebotlottunk a 2a + 2 kifejezésbe, mondhattuk róla, hogy osztható kettővel. Éppen azért, mert ez a feltevésünk. Ez a teljes indukció általában legnehezebb lépése – megérteni, mikor és miért használhatjuk az indukciós feltevést.

Ezzel az indukció véget ér, a bizonyítást sikeresen elvégeztük, a tétel igaz.

Ha akarnád, felbonthatnád másképp is, és nem kellene használnod a feltevést. p = 2n és q = 2 + 2. A q = 4 szám triviálisan osztható kettővel, és ugyanígy a p = 2n is, mert kettővel osztva megmarad az n szám, amely természetes, vagyis egész. Megint két olyan kifejezést kaptunk, amelyek mindegyike osztható kettővel, tehát az összegük is osztható kettővel.

Mindkét esetben azonban bebizonyítottuk, hogy

1. az adott kifejezés igaz n = 1-re,
2. ha a kifejezés igaz n-re, akkor igaz n + 1-re is.

Innen már levezethetjük:

• Tudjuk, hogy a kifejezés igaz n = 1-re.
• Ha igaz n-re, akkor igaznak kell lennie n + 1-re is, vagyis 1 + 1-re is, tehát a kifejezés igaz n = 2-re is.
• Ha igaz n-re, akkor igaznak kell lennie n + 1-re is, vagyis 2 + 1-re is, tehát a kifejezés igaz n = 3-ra is.
• Ha igaz n-re, akkor igaznak kell lennie n + 1-re is, vagyis 3 + 1-re is, tehát a kifejezés igaz n = 4-re is.
• Ha igaz n-re, akkor igaznak kell lennie n + 1-re is, vagyis 4 + 1-re is, tehát a kifejezés igaz n = 5-re is.
• …

Második példa

Ezután teljes indukcióval bebizonyítunk egy egyszerű állítást:

$$2^n\ge 2n;n\in {\mathbb{N}}^{+}.$$

Először az első lépés: megnézzük, hogy az állítás igaz-e n = 1-re, a pozitív egész számok első elemére, amelyből az n-et választjuk.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Ez triviálisan igaz. Most áttérünk az indukciós lépésre, amelyben meg kell néznünk, hogy ha igaz n = a-ra, akkor igaz-e n = a + 1-re is. A feltevésünk tehát az, hogy igaz

$$2^a\ge 2a$$

és be akarjuk bizonyítani, hogy

$$2^{a+1}\ge 2(a+1)$$

A bal oldalt először kifejtjük a hatványok számolási szabályaival, a jobb oldalon pedig egyszerűen felbontjuk a zárójelet.

$$2\cdot 2^a\ge 2a+2$$

A bal oldalon a szorzás helyett összeadást használunk, a jobb oldalt változatlanul hagyjuk.

$$2^a+2^a\ge 2a+2$$

Most felhasználjuk a feltevést. A feltevés olyan állítás, amelyről feltételezzük, hogy igaz. Az egyenlőtlenségben mindkét oldalon két-két összeadandó kifejezés áll. Ugyanakkor tudjuk, hogy

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

Az első sort a feltevés mondja, a második állítás triviális (a legkisebb 2^a az a = 1-re adódik, és az éppen kettő). Tudjuk tehát, hogy a bal oldalon mindkét kifejezés nagyobb vagy egyenlő, mint a jobb oldalon a megfelelő kifejezés. Ezzel teljes indukcióval bebizonyítottuk, hogy ha a kifejezés igaz a-ra, akkor igaz (a + 1)-re is, és mivel a kifejezés igaz az egyesre is, a megadott kifejezés igaz.

Harmadik példa

Próbáljuk meg bebizonyítani a következő állítást:

$$3\mid n\Rightarrow 3\mid n^2;n\in {\mathbb{N}}^{+}$$

Szavakkal: ha n osztható hárommal, akkor n² is osztható hárommal. Ha n nem osztható hárommal, akkor az állítás triviálisan igaz (az implikáció definíciója szerint), ezért azokkal az esetekkel foglalkozunk, amikor n osztható hárommal. Ez a pozitív egész számok egy sorozatát generálja: a_i=3, 6, 9, 12, 15… Mostantól ebben az a_i sorozatban mozgunk.

Az indukciós bizonyítást az első lépéssel kezdjük, vagyis hogy igaz-e az első elemre. Emlékeztetlek, hogy az a_i sorozatban mozgunk, tehát ennek a sorozatnak az első elemét vesszük, vagyis az a₁-et, ami a hármas. A hármasra a kifejezés igaz:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Most áttérünk az indukciós lépésre. Látjuk, hogy az a_i sorozat felírható 3n alakban, ahol n pozitív egész szám. A második elem tehát hárommal nagyobb az előzőnél, és így tovább. Most tegyük fel, hogy a kifejezés igaz n-re, és biztosítanunk kell, hogy igaz legyen (n + 3)-ra is, ami a következő elemet generáló szabály abban a sorozatban, amelyben mozgunk. Először felírjuk a feltevést:

$$3\mid n\Rightarrow 3\mid n^2$$

aztán azt, amit be akarunk bizonyítani

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

A másik oldalon felbontjuk a zárójelet a képlettel:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

És már majdnem a célnál vagyunk. A bal oldalon olyan kifejezés áll, amely biztosan osztható hárommal, mert az n a feltevés szerint osztható hárommal (csak az a_i sorozat számai között mozgunk), és a hármas is osztható hárommal. A jobb oldalon először az n² áll, amely a feltevés szerint osztható hárommal. Tudjuk ugyanis, hogy az n osztható hárommal, a feltevés pedig azt mondja, hogy ha az n osztható hárommal, akkor az n² is osztható hárommal:

$$3\mid n\Rightarrow 3\mid n^2$$

Ezután a 6n kifejezés következik, amely triviálisan osztható hárommal. Elképzelheted úgy, mint a tört egyszerűsítését:

$$\frac{6n}{3}=2n$$

Az n változó valamilyen pozitív egész szám, tehát a 2n szorzat is pozitív egész szám lesz, vagyis hárommal osztva pozitív egész számot kaptunk, így a 6n kifejezésnek oszthatónak kell lennie hárommal. A végén álló kilenc pedig megint osztható hárommal. A kifejezés igaz az első elemre és az indukciós lépésre is, tehát igaz.

A zárójelek száma egy kifejezésben

Az utolsó példa kissé szokatlan. Megpróbáljuk bebizonyítani azt az állítást, hogy az egyszerű kifejezésben a zárójelek száma mindig páros, hogy lásd, a teljes indukció teljesen más környezetben is használható, nemcsak a természetes számok között. Az elején meg kell határoznunk, mi az egyszerű kifejezés. Egyszerű kifejezés:

• pozitív egész szám,
• ha p egyszerű kifejezés, akkor (p²) is egyszerű kifejezés,
• ha p és q egyszerű kifejezések, akkor (p + q) is egyszerű kifejezés.

Tehát egyszerű kifejezés például: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). És ezek viszont nem egyszerű kifejezések:

• 1 + 2 → hiányzik a külső zárójel,
• (1 + 2 → hiányzik a jobb oldali zárójel,
• 13² → hiányzik a külső zárójel,
• (1 + 2 + 3) → hiányoznak a zárójelek, helyesen a felírás ez lenne: (1 + (2 + 3))

Az egyszerű kifejezés keletkezhet például így. Az elején választunk egy egyszerű kifejezést: (a + b). Most az a helyére behelyettesítünk egy egyszerű kifejezést, a = (c + d), így megkapjuk, hogy ((c + d) + b), a b helyére pedig behelyettesítjük a hármat: ((c + d) + 3). A c helyére behelyettesítjük a tízet: ((10 + d) + 3), végül a d helyére behelyettesítjük az (5²)-et: ((10 + (5²)) + 3). Fontos betartani a zárójeleket, különben nem fog működni.

Most bebizonyítjuk, hogy az egyszerű kifejezés páros számú zárójelet tartalmaz (a páros számok közé a nulla is beletartozik).

Az indukció első lépésében kiválasztunk valamilyen első elemet. Ebben az esetben az első elem a legtriviálisabb egyszerű kifejezés lesz, vagyis bármelyik pozitív egész szám. Tehát legyen

$$j=n;n\in {\mathbb{N}}^{+}.$$

A j kifejezésre igaz, hogy a zárójelek száma nulla, tehát az első elem megfelel. Az indukciós lépésben feltételezzük, hogy van két egyszerű kifejezésünk, p és q, és mindkettőben páros számú zárójel van. Ekkor be kell bizonyítanunk, hogy a (p + q) és a (p²) egyszerű kifejezésekben is páros számú zárójel van.

Először az összeadás. Definiálunk még egy z(q) függvényt, amely a q kifejezés zárójeleinek számát adja vissza. Ekkor a (p + q) kifejezésben z(p) + z(q) + 2 zárójel van. Tehát kettővel több zárójele van, mint a p és q kifejezések zárójelei számának összege. A feltevés szerint a z(p) és a z(q) is páros, tehát ha három páros számot összeadunk, megint páros számot kapunk. Erre az esetre az állítás igaz.

Most a hatványra. Megint érvényes a feltevés, hogy a p egyszerű kifejezés páros számú zárójelet tartalmaz. A (p²) kifejezés ekkor z(p) + 2 zárójelet tartalmaz, vagyis megint kettővel többet, mint a p kifejezés. Ebben az esetben is páros számokat adunk össze, az eredmény tehát páros.

Az állítás igaz az első elemre, és igaz az indukciós lépésben is, ezért az állítás igaz.