Induktion:

En induktion är en SannolikSlutledning, till skillnad från Deduktion. Man jämför olika fall med varandra och drar slutsatsen efter erfarenheten att det sista fallet också mot förmodan slutar på samma vis som de tidigare. Ex: Man kan dra slutsatsen att alla SimonKågedal spelar Punk. Då menar man att alla SimonKågedal som man hittills sett i sitt liv har spelat Punk. Ett induktionsbevis kan delas in i två steg:

1. Bevisa att påståendet gäller i FörstaFallet. ("Basfallet")
2. Bevisa att om påståendet gäller för VilketFallSomHelst, så måste det gälla för nästa fall. (InduktivtFall)

Matematisk Induktion

1. 0 ar ett naturligt tal
2. Om n ar ett naturligt tal, sa ar dess efterfoljare, n+1, ocksa ett naturligt tal.

Nu har vi definerat en InduktivStruktur som vi sedan kan utfora bevis pa.

Exempel

Hypotes: For varje naturligt tal n galler att kvadraten av n ar lika med summan av alla (2*i-1), dar i gar fran 1 till n.

Det ar enkelt att kolla att detta galler for ett godtyckligt naturligt tal:

0 * 0 = 0 = 0 (det finns inga naturliga tal mellan 1 och 0)

1 * 1 = 1 = (2*1-1)

2 * 2 = 4 = (2*1-1) + (2*2-1)

3 * 3 = 9 = (2*1-1) + (2*2-1) + (2*3-1)

Nu galler det att overtyga oss sjalva om att detta galler for ALLA naturliga tal. Har kommer induktion in i bilden.

Basfall

Har ska vi bevisa att formeln galler for talet 0. Det har vi ju redan gjort ovan.

Induktivt fall

Har ska vi bevisa, att Om formeln galler for ett tal n, sa galler det aven for talet n+1.

Vi ska alltsa Anta att det galler for talet n, och sedan visa att det galler for n+1.

Vi vet: n*n = summa[i gar fran 1 till n] (2*i-1)

Vi vill visa: (n+1)*(n+1) = summa[i gar fran 1 till n+1] (2*i-1)

Har foljer beviset:

(n+1)*(n+1) = [vanlig aritmetik]

n*n + 2*n + 1 = [induktion]

summa[i gar fran 1 till n] (2*i-1) + 2*n + 1 = [hopslagning av summor]

summa[i gar fran 1 till n+1](2*i-1)

Har ar alltsa beviset fardigt.

Sök på Hörnan.    Titelsökning:    Textsökning:    Liknande sidor    Sidkarta

Besök oss också gärna på våran fina chat!

Hörnan - en kärleksfull webbsida