Teljes indukció. Segítenél?

Először is, ez egy bizonyítási módszer. Egy adott állítást (sejtést) igazolhatunk vele

Vegyük például az első n pozitív egész szám összegét ami n(n+1)/2

3 lépésből áll!

1. lépés:

Megnézzük konkrét esetekre fennáll-e az állítás. Így tulajdonképpen már az elején kizárhatjuk azokat a sejtéseket amikre ez nem áll fenn, és nem a végén, sok munka után derül ki, hogy ez biztos hülyeség.

Tehát nézzük azt, ha n=1 ennek az összege 1 visszahelyettesítve pedig hálistennek 1*2/2=1-et kapunk ; 1=1 eddig ok

Ha n=2 az első két szám 1 és 2, ezek összege: 1+2=3 , behelyettesítve pedig 2*3/2=3 ; 3=3 Jó!

(Érdemes kb. 2-3 számot kipróbálni, és ha rendben vannak, továbbmehetünk)

2. lépés: Feltesszük a sejtést: Tegyük fel hogy az első n pozitív egész szám összege n(n+1)/2

3. lépés: Be kell bizonyítani, hogy az első n+1 pozitív egész szám összege (Figyelem n-ből n+1 lesz) (n+1)(n+1+1)/2 azaz (n+1)(n+2)/2

Célszerű megjeleníteni a 2. lépésben feltett állítást. Tehát felbontva:

(n+1)(n+2)/2= n(n+1)/2 + 2*(n+1)/2

Na a 2. lépés kimondja, hogy n(n+1)/2 az első n poz. egész összege, azaz 1+2+...+n

Egyszerűsítve:

(n+1)(n+2)/2= 1+2+...+n + (n+1)

Tehát igaz a 3. lépésben feltett állítás. Tehát a sejtésünk igaz.

15:35 jól leírta, azért néhány kiegészítést tennék.

1) Az első lépés nem csak azért érdekes, hogy megbizonyosodjunk róla, hogy feltehetőleg igaz az, amit be akarunk bizonyítani, elméletileg is fontos része ez a bizonyításnak. Elméletileg elegendő egyetlen egy esetre megnézni (de legalább egyre muszáj!), de a gyakorlatban tényleg jó ötlet 2-3-ra is megnézni, mert abból esetleg jöhetnek ötletei az embernek, hogy hogyan lehet majd bizonyítani.

2) Én úgy szoktam inkább mondani a második lépést, hogy feltételezzük, hogy n=k-ra igaz. Vagyis bevezetek egy k nevű sorszámot. n-nel is jó, de számomra logikusabb, hogy máshogy hívom a közbülső elemet.

3) A harmadik lépésben az a fontos, hogy a (k+1)-hez tartozó összefüggést át kell alakítani úgy, hogy benne legyen a k-hoz tartozó kifejezés, és ekkor a 2. lépés összefüggését ki tudjuk használni. Ebből már kijön a bizonyítás.

Nézzünk egy másik példát:

Bizonyítandó: Az első n darab páratlan szám összege n².

(megjegyzés: az n-edik páratlan szám így írható fel: 2n-1

Ezt könnyű belátni, teljes indukcióval be is lehet bizonyítani, majd a végén próbáld meg.)

1) n=1-re megnézzük: Az első páratlan szám az 1, ez tényleg 1².

Ennyi elegendő elméletileg, de azért a magunk megnyugtatására nézzük meg n=2-re is:

első: 1

második: 3

1+3 = 2², tényleg igaz.

2) Feltételezzük, hogy n=k-ra igaz. Ezt most le is írom, mert a kővetkező lépésben ezt felhasználva tudunk majd továbbmenni:

Az első k darab páratlan szám összege k². (A k-adik páratlan szám a 2k-1 volt.)

k=1-re már megnéztük hogy igaz, k=2-re is, de most feltettük, hogy egy tetszőleges valamilyen középső sorszámra igaz.

3) Kiszámoljuk, hogy n=k+1 esetén mi lesz:

A számok, amiket összeadunk:

1,3,...,2k-1 és 2(k+1)-1

Most jön a trükk: észrevesszük, hogy a számok eleje az "és" előtt éppen az első k darab szám, és annak összegéről az előző pontban feltételeztük, hogy éppen k². Vagyis a fenti számok összege:

k² + 2(k+1)-1

ami

k²+2k+1

erről viszont tudjuk, mert tanultuk, hogy éppen (k+1)².

Vagyis mi jött ki? Az, hogy az első k+1 darab páratlan szám összege (k+1)². Vagyis ha feltételezzük, hogy n=k-ra igaz, akkor bebizonyítottuk, hogy n=k+1-re is igaz.

Készen is vagyunk, ezzel a teljes indukciós bizonyítás sikerült.

Ha nem absztraktan akarod megérteni, hogy ez miért is bizonyítja be tényleg az összes n-re a tételt, gondolj bele ebbe:

n=1-re kipróbáltuk az 1) pontban, igaz volt.

n=2-re is kipróbáltuk, igaz.

n=3-ra azért igaz, mert ha 2-nek vesszük a k-t, akkor arra a 2) lépés tényleg teljesül, nem csak feltesszük hogy igaz, de meg is néztük. A 3) lépés miatt pedig k+1-re, vagyis 3-ra is bebizonyítottuk, hogy igaz.

n=4-re azért igaz, mert ha k=3-at nézzük, arra most az előbb kijött, hogy tényleg igaz, tehát ez felhasználható 2) pontként. A 3) pont miatt viszont tuti, hogy k+1=4-re is igaz.

n=5-re azért igaz, ... és így tovább a végtelenségig, tényleg bármelyik n-re igaz lesz.

A 3. pont az n=k+1 eset. A k+1-edik páratlan szám:

2(k+1)-1

Ha nem érted, szólj, hosszabban magyarázom.

Először kell a dologhoz egy sejtés: Az első n egész szám köbének összege n²·(n+1)²/4

1) n=1-re: 1²·2²/4 = 1, igaz.

csak a biztonság kedvéért: n=2-re: 2²·3²/4 = 9, és 1+8 tényleg 9, továbbra is igaz.

2) feltesszük n=k-ra, hogy 1³+2³+...+k³ = (k·(k+1)/2)²

3) megnézzük n=k+1-re:

Az összeadandó számok:

1³+2³+...+k³+(k+1)³

az első k tag összegét tudjuk a 2. pont szerint: k²·(k+1)²/4

Ehhez kell hozzáadni ezt: (k+1)³ = (k+1)·(k+1)²

k²·(k+1)²/4 + (k+1)(k+1)²

kiemelünk (k+1)²-t:

(k+1)²·(k²/4 + k+1)

közös nevező 4:

(k+1)²·(k²+4k+4)/4

észrevesszük, hogy a k²+4k+4 egy nevezetes négyzet:

(k+1)²·(k+2)²/4

és ez már a kívánt kifejezés, hisz n=k+1 miatt ez éppen

n²·(n+1)²/4

Kész.

Bocsánat, menet közben módosítottam kicsit a kifejezés formáján, hogy egyszerűbb legyen a bizonyítás, de a 2-es pontnál a régi forma maradt ott véletlenül. Így érthetőbb:

2) feltesszük n=k-ra, hogy 1³+2³+...+k³ = k²·(k+1)²/4

(a fenti 2. pont is igaz, csak úgy nehezebb megérteni egy picit)