Induktion (matematik)

Wikipedia

Matematisk induktion är en matematisk angreppsmetod för att bevisa satser om naturliga tal, eller mer generellt om ordinaltal. Beviset går vanligen ut på att visa ett basfall och sedan visa att om förhållandet gäller för ett värde så gäller det även för det nästföljande värdet. Induktionsbevis baserar sig på de egenskaper hos de naturliga talen som beskrivs i Peano-postulaten.

[redigera] Induktionsprincipen

Låt $P n$ vara en utsaga om ett naturligt tal n, och antag att följande påståenden är sanna:

$P 0$ är sann.
$\forall p \in \mathbb{N}:P_p \Rightarrow P_{p+1}$ .

Då är $P n$ sann för alla naturliga tal n.

[redigera] Ett första exempel

Sats att bevisa:

$1+2+3+...+n=\frac{n(n+1)}{2}$ , där n är ett naturligt tal.

Visa först att det gäller för ett basfall n=1, vänsterledet är ju givetvis 1. För högerledet får vi att:

$\frac{n(n+1)}{2} \Rightarrow \frac{(1)(1+1)}{2}=1\,$ då n=1. Därmed har vi visat att satsen gäller för n=1.

Om vi nu antar att satsen gäller för ett godtyckligt tal n=k, så återstår det att visa att detta medför att det även är sant för $n = k + 1$ .

Antagande: $1+2+3+...+k = \frac{k(k+1)}{2}$

För $n = k + 1$ gäller då att visa att: $1+2+3+...+k+(k+1) = \frac{(k+1)(k+2)}{2}$

I vänsterledet är termerna upp till k vårt antagande, som vi nu drar nytta av:

$1+2+3+...+k+(k+1)= \frac{k(k+1)}{2}+(k+1) =\frac{k(k+1)}{2}+\frac{2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$

Eftersom vi har visat att satsen gäller för n=1, och om det är sant för n=k så är det även sant för n=k+1, så säger induktionsprincipen att satsen är sann för alla naturliga tal $n\ge1$ .

[redigera] Ett andra exempel

Man kan också göra tvärtom för att visa att om ett påstående är falskt för n=p, så är det även falskt för n=p+1. Detta används i följande bevis.

Bevisa att för varje naturligt tal n är talet $3 2 n + 1 + 5 2 n$ delbart med 4, men inte med 8.

Bevis: Förenkling ger $k = 3 2 n + 1 + 5 2 n = 3 * 3 2 n + 5 2 n = 3 * 9 n + 25 n$

För n=0 gäller alltså att $k 0 = 3 + 1 = 4$ , och för n=1 fås att $k 1 = 3 * 9 + 25 = 52$ . Både 4 och 52 är delbara med 4, men inte för 8. Nu har vi visat att det gäller för två basfall.

Antag nu att det är sant för n=p+1 (att det är delbart med 4), alltså $k p + 1 = 27 * 9 p + 25 * 25 p$ , då gäller för n=p+2:

$k p + 2 = 27 * 9 p + 1 + 25 * 25 p + 1$
$k p + 2 = 27 * 9 p + 1 + 25 * 25 p + 1 + 216 * 9 p - 216 * 9 p + 600 * 25 p - 600 * 25 p$
$k p + 2 = (27 * 9 p + 25 * 25 p) + 216 * 9 p + 600 * 25 p$

Där parentesen motsvarar vårt antagande, som alltså skulle vara delbart med 4. 216 och 600 är båda delbara med 4, och således är även hela uttrycket delbart med 4. Induktionsprincipen ger att $3 2 n + 1 + 5 2 n$ är delbart med 4 för alla naturliga tal n.

Om vi antar att $k p + 1$ är delbart med 8, så visar det alltså sig att även $k p + 2$ är delbart med 8, eftersom 216 och 600 är det. Problemet här är att vi inte kan påbörja induktionen eftersom vi inte har något basfall. Om vi däremot hade antagit att det var falskt för $k p + 1$ , hade vi funnit med samma metod som ovan att det även är falskt för $k p + 2$ . Då det är falskt för basfallen n=0 och n=1 (att det är delbart med 8), säger induktionsprincipen att $3 2 n + 1 + 5 2 n$ inte är delbart med 8 för alla naturliga tal n, och det ursprungliga påståendet har bevisats.

[redigera] Metafor till induktionsantagandet

För att inte allt ska bli för abstrakt med tal och variabler kan du tänka dig att du står på på ett trappsteg, anta sedan att du kan ta dig till vilket trappsteg som helst (k), utifrån det antagandet är sant ska du sedan bevisa att du kan ta dig till ett trapsteg högre (k + 1).

Den här artikeln är hämtad från http://sv.wikipedia.org../../../i/n/d/Induktion_%28matematik%29.html

Kategorier: Matematiska grundbegrepp | Logik