Induktion (matematik)

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.

Principen för matematisk induktion

Låt A vara en mängd av positiva heltal som innehåller talet ett. Om A innehåller talet n+1 då det även innehåller talet n, så är A lika med mängden av alla positiva heltal.

Denna formulering kan man bevisa på ett elegant sätt med hjälp av välordningsaxiomet för de positiva heltalen.

Bevis av principen för matematisk induktion

Beteckna med A mängden av alla de positiva heltal som innehåller talet ett, och talet n+1 då det innehåller talet n.

Antag att A inte är lika med mängden av alla positiva heltal.

Då finns det positiva heltal som ligger utanför mängden A. Samla ihop dessa till en mängd som betecknas med B. Mängden B är en icke-tom mängd bestående av positiva heltal. Enligt välordningsaxiomet för de positiva heltalen innehåller B ett minsta element, som betecknas med m. Eftersom mängden A innehåller talet ett, kan m inte vara talet ett; det är därför större än talet ett. Då är m-1 ett positivt heltal som är mindre än m. Talet m-1 kan inte ligga i mängden B, eftersom m-1 då vore det minsta elementet i B. Därför måste talet m-1 ligga i mängden A. Om m-1 ligger i mängden A. så ligger talet (m-1) + 1 också i mängden A. Detta innebär att talet m ligger i mängden A. Men talet m ligger ju utanför mängden A (i mängden B) och detta är omöjligt.

Det var därför fel att anta att mängden A inte var lika med mängden av positiva heltal.

Härmed är principen om matematisk induktion bevisad.

Exempel

Nedan följer några exempel där man kan använda principen om matematisk induktion för att bevisa olika påståenden om positiva heltal.

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

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^{2n+1}+5^{2n}$ delbart med 4, men inte med 8.

Bevis: Förenkling ger

k=3^{2n+1}+5^{2n}=3*3^{2n}+5^{2n}=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^{2n+1}+5^{2n}$ ä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^{2n+1}+5^{2n}$ inte är delbart med 8 för alla naturliga tal n, och det ursprungliga påståendet har bevisats.

Ett tredje exempel

För att få en uppfattning om storleken hos talen n-fakultet (n!) skall vi visa att:

n! \leq n^n, \qquad n = 1,2,3,\dots \,.

För det första gäller olikheten då n=1, eftersom 1!=1. Vi antar att olikheten gäller för talet n=N och skall visa att den även gäller för nästa heltal, N+1.

(N+1)! = N! \, (N+1) \leq N^N \, (N+1) \leq (N+1)^N \, (N+1) = (N+1)^{N+1}.

Enligt principen för matematisk induktion gäller olikheten för alla positiva heltal, 1,2,3,... .

Metaforer 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).
Ett annat sätt att uppfatta principen för matematisk induktion är att se det som uppradade dominobrickor: När man välter den första brickan (n=1) välts de andra i tur och ordning. (Dominobrickorna representerar de positiva heltalen.)