Matematikai indukció

A matematikai indukció egy bizonyítási módszer, amellyel azt mutatjuk meg, hogy egy állítás minden természetes számra igaz. Különösen hasznos sorozatok, összegképletek és oszthatósági állítások bizonyításában.

Az indukció lépései

• 1. Alapeset: igazoljuk az állítást az első számra (általában n=1).
• 2. Indukciós feltevés: feltesszük, hogy az állítás igaz n-re.
• 3. Indukciós lépés: bebizonyítjuk, hogy ha igaz n-re, akkor igaz n+1-re is.

Egyszerű példa

Bizonyítsuk, hogy az első n természetes szám összege a következő képlettel adható meg:

1. Alapeset: n=1 esetén bal oldal = 1, jobb oldal = 1·(1+1)/2 = 1 → igaz. 2. Tegyük fel, hogy igaz n-re. 3. Indukciós lépés: összeadva n+1-et is, a képlet n+1-re is igaz lesz. Ezzel beláttuk az állítást minden n-re.

Általános séma

Az indukciós bizonyítás lényege, hogy a bizonyítási láncot sosem kell minden n-re külön elvégezni: elég az alaplépést és az indukciós lépést bizonyítani, így minden további esetre automatikusan igaz lesz.

Mikor használjuk?

• Összegképletek bizonyításánál.
• Osztási tulajdonságoknál (pl. egy szám mindig osztható valamivel).
• Rekurzív definíciók helyességének igazolására.
• Számelméleti tételeknél.

Összefoglalás

A matematikai indukció módszerével beláthatjuk, hogy egy állítás minden természetes számra igaz. Két fő része van: alapeset és indukciós lépés. Ez az egyik legfontosabb bizonyítási technika a matematikában.

Gyakorló feladat