Matematikai indukció: definíció, bizonyítási elv és példák

Matematikai indukció: világos definíció, indukciós bizonyítás elve és gyakorlati példák természetes számokra — lépésről lépésre magyarázat a gyors megértéshez.

A matematikai indukció egy nagyon fontos bizonyítási módszer, amelyet leggyakrabban olyan állítások igazolására használunk, amelyek valamennyi természetes számra (vagy azok egy kezdőértékétől kezdve minden további egészre) teljesülnek. Az indukció alapgondolata egyszerű: megmutatjuk, hogy az állítás igaz az első (vagy egy adott) esetre, majd igazoljuk, hogy ha igaz egy tetszőleges n-re, akkor igaz a következő, n+1-re is. Ebből következik, hogy az állítás minden természetes számra igaz.

A bizonyítás általános szerkezete

• Alapeset (bázis): Igazoljuk az állítást egy kiinduló értéknél (általában n = 1 vagy n = 0, de lehet más kezdőérték is).
• Indukciós feltevés (indukciós hipotézis): Tegyük fel, hogy az állítás igaz egy tetszőleges, de rögzített n = n0 esetén.
• Indukciós lépés: Az indukciós feltevés felhasználásával bizonyítsuk be az állítást n = n0 + 1-re.
• Ha ezek teljesülnek, akkor az állítás a bázistól kezdve minden további egészre igaz lesz (1-re, 2-re, 3-ra, ...).

Fontos megjegyzések

• Az indukció helyes megfogalmazása és a pontos feltételek megadása kulcsfontosságú. Mindig jelöljük meg, hogy melyik n-től kezdve állítjuk, hogy az állítás érvényes.
• Létezik a klasszikus (gyenge) indukció mellett az ún. erős indukció (vagy teljes indukció), ahol az indukciós feltevés nemcsak az n0 esetet foglalja magában, hanem minden k ≤ n0 esetét feltételezhetjük, és ezekből következtetünk n0+1-re. Ezt gyakran használjuk például számelméleti állításoknál vagy rekurrens képletek vizsgálatánál.
• Gyakori hiba: az indukciós feltételezés (azaz amit „feltételezünk” n-re) nem lehet ugyanaz, mint amit bizonyítunk — azt kell feltételezni, hogy az állítás igaz n-re, és ebből kell levezetni, hogy igaz n+1-re. Nem szabad anélkül "beugrani", hogy az indukciós feltevés valóban különböző legyen a céltól.
• Előfordulhat, hogy több kezdőbázist kell igazolni (például ha az állítás csak n ≥ 5-től érvényes, vagy az indukciós lépésnél n+1-hez a korábbi több eset szükséges).

Típushibák — egy klasszikus példa

Az egyik híres "hamis indukciós" érvelés az a bizonyítás, amely azt állítja, hogy „minden ló ugyanolyan színű”. Az érvelés az indukció hagyományos szerkezetét követi, de a hiba a helytelen átvitelben rejlik, amikor az alapeset kiterjesztése a következő esetre (n=1-ről n=2-re) nem biztosítja, hogy a két lóhalmaz között közös elem legyen. Ez jól szemlélteti, hogy az indukció működése formális feltételektől függ, és egy-egy hiányzó összekötő lépés tönkreteheti az egész érvelést.

Példa: az 1 + 2 + ... + n = n(n+1)/2 összeg formula

Az alábbi, eredeti példa szemlélteti a klasszikus indukciós bizonyítást. (A képletek és ábrák az eredeti forrásnak megfelelően szerepelnek.)

A matematikai indukció a matematikai igazság bizonyításának egy speciális módja. Ezzel bizonyíthatjuk, hogy valami igaz az összes természetes számra (az összes pozitív egész számra). Az elképzelés az, hogy

• Valami igaz az első esetre
• Ugyanez mindig igaz a következő esetre is.

majd

• Ugyanez igaz minden esetben.

A matematika óvatos nyelvén:

• Állapítsa meg, hogy a bizonyítás n {\displaystyle n} fölött indukcióval történik. ( n {\displaystyle n} az indukciós változó.)
• Mutassuk meg, hogy az állítás igaz, ha n {\displaystyle n} 1.
• Tegyük fel, hogy az állítás igaz bármely n természetes számra {\displaystyle n} . (Ezt nevezzük indukciós lépésnek.)
• Mutassuk meg, hogy az állítás igaz a következő számra, n + 1 {\displaystyle n+1} .

Mert igaz az 1-re, akkor igaz az 1+1-re (=2, az indukciós lépés alapján), akkor igaz a 2+1-re (=3), akkor igaz a 3+1-re (=4), és így tovább.

Példa az indukciós bizonyításra:

Bizonyítsuk be, hogy minden n természetes számra:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}}n(n+1)}

Bizonyíték:

Először is, az állítás felírható: minden n természetes szám esetén

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)}

Indukcióval n-re,

Először is, n=1 esetén:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} ,

tehát ez igaz.

Ezután tegyük fel, hogy bizonyos n=n0 esetén az állítás igaz. Vagyis:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}}k=n_{0}(n_{0}+1)}

Ezután n=n0+1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k}k}

átírható

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}

Mivel 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\displaystyle 2\sum _{k=1}^{n_{0}}}k=n_{0}(n_{0}+1),}

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)}

A bizonyítás tehát helyes.

További példák és gyakorlat

• Indukcióval gyakran bizonyítanak különböző sorozatokra, egyenlőtlenségekre (például n! ≥ 2^{n-1} bizonyítása megfelelő kezdőértékkel), vagy arra, hogy egy visszavezető képlet minden n-re ad értelmes eredményt.
• Gyakorlatként próbálja meg: bizonyítsa indukcióval, hogy 2^n ≥ n+1 minden n ≥ 1-re; illetve bizonyítsa be, hogy n^2 ≤ 2^n minden n nagyobb vagy egyenlő 5-tel.
• Amikor indukciós bizonyítást olvas vagy ír, mindig ellenőrizze: 1) világos-e a bázis, 2) pontosan van-e megfogalmazva az indukciós hipotézis, 3) helyes-e az a lépés, amely n-ről n+1-re vezet.

Összefoglalva: a matematikai indukció egy nagyon erős és formális módszer, amely lehetővé teszi, hogy végtelen sok esetet egyetlen, jól felépített kétlépcsős bizonyítással igazoljunk. Figyeljünk a bázisra és az indukciós lépés gondos megindoklására!

Kérdések és válaszok

K: Mi az a matematikai indukció?

K: Hogyan zajlik az indukciós bizonyítás?

K: Mit jelent az induktív lépésben feltételezni valamit?

K: Milyen számokat használnak a matematikai indukcióban?

K: Hogyan lehet megmutatni, hogy valami igaz a következő számra (n+1)?

Keresés betűvel