Induktionsbevis

Matematisk induktion är en ofta använd bevismetod i matematiken, oftast när vi arbetar med positiva heltal eller med någon annan talföljd.

Principen

Grundprincipen är att vi bevisar det givna påståendet för något första element, bland de positiva heltalen oftast n = 1. Det bevisar vi genom att helt enkelt sätta in värdet. I nästa steg, induktionssteget, bevisar vi implikationen ”om påståendet gäller för n = a, så gäller det också för n = a + 1”.

Av de här två stegen kan vi dra slutsatsen att det givna uttrycket gäller för alla n (ur den mängd som vi just arbetar med). Varför är det så? I början bevisar vi att uttrycket gäller för n = 1. Samtidigt vet vi att om uttrycket gäller för n = a, så gäller det också för n = a + 1. Vi väljer alltså a = 1. Vi vet att uttrycket gäller för a = 1 och också att det gäller för a + 1 = 2. Nu vet vi att uttrycket gäller för a = 2. Men eftersom det också gäller för a + 1, måste det gälla även för 2 + 1 = 3. Och så vidare.

Första exemplet

Det första exemplet blir trivialt. Vi bevisar att om vi lägger till två till vilket jämnt tal som helst, så får vi återigen ett jämnt tal. Eftersom vi rör oss bland de positiva heltalen skriver vi ett allmänt jämnt tal som 2n, där n är ett positivt heltal. Om vi sätter in vilket positivt heltal som helst för n, får vi ett jämnt tal som resultat, det syns direkt. Delbarhet skrivs med ett lodrätt streck så här:

$$2\mid 2n$$

Det här skrivsättet betyder att tvåan delar uttrycket 2n utan rest. Nu när vi kan skriva delbarhet kan vi också skriva det som vi ska bevisa med matematisk induktion.

$$2\mid 2n+2;n\in {\mathbb{Z}}^{+}$$

Det här ska vi alltså bevisa i det första exemplet, att tvåan delar uttrycket 2n + 2 — det motsvarar precis den ursprungliga formuleringen i ord ”om vi lägger till två till vilket jämnt tal som helst, så får vi återigen ett jämnt tal”.

I det första steget av induktionen bevisar vi det för det första elementet, för ettan. Vi sätter in n = 1 i uttrycket:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

Tvåan delar fyran utan rest, så för det första elementet gäller det. Därefter kommer induktionssteget, där vi ska bevisa att om det gäller för det a:te elementet, så gäller det också för element nummer (a + 1). Från början antar vi att vårt antagande gäller, alltså n = a:

$$2\mid 2a+2$$

Det här uttrycket antar vi är sant — det använder vi när vi konstruerar beviset. Nu vill vi bevisa att

$$2\mid 2(a+1)+2.$$

Vad har vi gjort? Vi har skrivit (a + 1) på a:s plats. Parenteserna är viktiga, det här uttrycket vore fel: 2a + 1 + 2. Vi lägger inte till ett till hela uttrycket, utan vi gör verkligen a till ett uttryck som är ett större, alltså (a + 1). Uttrycket skriver vi om genom att utveckla parentesen.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Nu en liten avstickare till delbarhet. Om vi har två tal, låt oss säga p och q, som är delbara med något tal, till exempel r, så gäller att också deras summa är delbar med r. Alltså gäller:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Vi kan sätta in till exempel talen p = 8, q = 20 och r = 4. Vi ser att fyran delar både åttan och tjugan. Och likaså delar den deras summa 8 + 20 = 28.

Hur utnyttjar vi det i vårt exempel? Vi delar upp högra sidan i talen p och q så här:

$$p=2a+2;q=2$$

Talet q, alltså tvåan, är trivialt delbart med två. Och uttrycket p är också delbart med två, eftersom antagandet säger det. Uttrycket p motsvarar precis vårt antagande, som vi antar är sant. Och om p är delbart med två och samtidigt q är delbart med två, då är också deras summa delbar med två.

Ännu en gång om antagandet. I början sa vi att vi antar att

$$2\mid 2a+2.$$

När vi därför under konstruktionen av beviset stötte på uttrycket 2a + 2, kunde vi säga att det är delbart med två. Just därför att det är vårt antagande. Det här brukar vara det svåraste steget i matematisk induktion — att förstå när och varför man kan använda induktionsantagandet.

Därmed är induktionen slut, beviset är genomfört, satsen gäller.

Om du vill kan du dela upp det på ett annat sätt och slippa använda antagandet. p = 2n och q = 2 + 2. Talet q = 4 är trivialt delbart med två och likaså p = 2n, eftersom vi efter division med två får talet n, som är ett positivt heltal, alltså ett heltal. Återigen har vi fått två uttryck som båda är delbara med två, så också deras summa är delbar med två.

I båda fallen har vi dock bevisat att

1. det givna uttrycket gäller för n = 1,
2. om uttrycket gäller för n, så gäller det också för n + 1.

Därifrån kan vi sluta oss till:

• Vi vet att uttrycket gäller för n = 1.
• Om det gäller för n, måste det gälla för n + 1, alltså också för 1 + 1, alltså gäller uttrycket också för n = 2.
• Om det gäller för n, måste det gälla för n + 1, alltså också för 2 + 1, alltså gäller uttrycket också för n = 3.
• Om det gäller för n, måste det gälla för n + 1, alltså också för 3 + 1, alltså gäller uttrycket också för n = 4.
• Om det gäller för n, måste det gälla för n + 1, alltså också för 4 + 1, alltså gäller uttrycket också för n = 5.
• …

Andra exemplet

Härnäst bevisar vi ett enkelt påstående med matematisk induktion:

$$2^n\ge 2n;n\in {\mathbb{Z}}^{+}.$$

Först det första steget, vi undersöker om påståendet gäller för n = 1, som första element bland de positiva heltal som vi väljer n ur.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Det gäller trivialt. Nu går vi över till induktionssteget, där vi måste undersöka om det, när det gäller för n = a, också gäller för n = a + 1. Vårt antagande är alltså att

$$2^a\ge 2a$$

gäller, och vi vill bevisa:

$$2^{a+1}\ge 2(a+1)$$

Vänstra sidan skriver vi först om med hjälp av räknereglerna för potenser och högra sidan utvecklar vi helt enkelt.

$$2\cdot 2^a\ge 2a+2$$

På vänstra sidan använder vi addition i stället för multiplikation, den högra lämnar vi oförändrad.

$$2^a+2^a\ge 2a+2$$

Nu utnyttjar vi antagandet. Ett antagande är ett påstående som vi antar gäller. I olikheten har vi på båda sidor en summa av två uttryck. Samtidigt vet vi att

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

Den första raden får vi från antagandet och det andra påståendet är trivialt (det lägsta 2^a fås för a = 1 och det är just lika med två). Vi vet alltså att på vänstra sidan är båda uttrycken större än eller lika med båda uttrycken på högra sidan. Därmed har vi med induktion bevisat att om uttrycket gäller för a, så gäller det också för (a + 1), och eftersom uttrycket också gäller för ettan, är det givna uttrycket sant.

Tredje exemplet

Vi försöker bevisa följande påstående:

$$3\mid n\Rightarrow 3\mid n^2;n\in {\mathbb{Z}}^{+}$$

Med ord: om n är delbart med tre, så är också n² delbart med tre. Om n inte är delbart med tre, så gäller uttrycket trivialt (enligt definitionen av implikation), så vi ägnar oss åt fallen där n är delbart med tre. Det ger oss talföljden av positiva heltal a_i=3, 6, 9, 12, 15… Från och med nu rör vi oss i den här talföljden a_i.

Induktionsbeviset börjar vi med första steget, alltså med att undersöka om det gäller för det första elementet. Jag påminner om att vi rör oss i talföljden a_i, så vi tar det första elementet i den här talföljden, alltså elementet a₁, som är tre. För trean gäller uttrycket:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Nu går vi över till induktionssteget. Vi ser att talföljden a_i kan skrivas som 3n, där n är ett positivt heltal. Det andra elementet är alltså tre större än det föregående osv. Anta nu att uttrycket gäller för n. Vi måste se till att det också gäller för (n + 3), vilket är den regel som skapar nästa element i den talföljd där vi rör oss. Först skriver vi antagandet:

$$3\mid n\Rightarrow 3\mid n^2$$

och sedan det vi vill bevisa

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Vi utvecklar parentesen på andra sidan med hjälp av formeln:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

Och nu är vi nästan i mål. På vänstra sidan har vi ett uttryck som säkert är delbart med tre, eftersom n enligt antagandet är delbart med tre (vi rör oss bara bland talen i talföljden a_i) och trean också är delbar med tre. På högra sidan har vi först n², som enligt antagandet är delbart med tre. Vi vet nämligen att n är delbart med tre och antagandet säger att om n är delbart med tre, så är också n² delbart med tre:

$$3\mid n\Rightarrow 3\mid n^2$$

Därefter följer uttrycket 6n, som är trivialt delbart med tre. Du kan tänka dig det som förkortning av ett bråk:

$$\frac{6n}{3}=2n$$

Variabeln n är något positivt heltal, så också produkten 2n blir ett positivt heltal, alltså fick vi ett positivt heltal efter division med tre, och uttrycket 6n måste därför vara delbart med tre. Och nian på slutet är återigen delbar med tre. Uttrycket gäller för första elementet och för induktionssteget, så det är sant.

Antalet parenteser i ett uttryck

Det sista exemplet blir lite ovanligt. Vi försöker bevisa påståendet att antalet parenteser i ett enkelt uttryck alltid är jämnt, så att du ser att matematisk induktion kan användas i ett helt annat sammanhang än bara bland positiva heltal. Först måste vi definiera vad ett enkelt uttryck är. Ett enkelt uttryck är:

• ett positivt heltal,
• om p är ett enkelt uttryck, så är också (p²) ett enkelt uttryck,
• om p och q är enkla uttryck, så är också (p + q) ett enkelt uttryck.

Enkla uttryck är alltså till exempel: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Och tvärtom, det här är inte enkla uttryck:

• 1 + 2 → de yttre parenteserna saknas,
• (1 + 2 → den högra parentesen saknas,
• 13² → de yttre parenteserna saknas,
• (1 + 2 + 3) → parenteser saknas, rätt skrivet skulle det vara (1 + (2 + 3))

Ett enkelt uttryck kan till exempel bildas så här. I början väljer vi ett enkelt uttryck (a + b). Nu sätter vi in det enkla uttrycket a = (c + d) för a, så vi får ((c + d) + b), och för b sätter vi in en trea: ((c + d) + 3). För c sätter vi in en tia: ((10 + d) + 3) och till sist sätter vi in (5²) för d: ((10 + (5²)) + 3). Det är viktigt att hålla reda på parenteserna, annars fungerar det inte.

Nu bevisar vi att ett enkelt uttryck innehåller ett jämnt antal parenteser (till de jämna talen räknas också noll).

I det första steget av induktionen väljer vi något första element. I det här fallet blir det första elementet det mest triviala enkla uttrycket, alltså vilket positivt heltal som helst. Vi sätter alltså

$$j=n;n\in {\mathbb{Z}}^{+}.$$

För uttrycket j gäller att antalet parenteser är noll, så det första elementet uppfyller villkoret. I induktionssteget antar vi att vi har två enkla uttryck p och q och att båda har ett jämnt antal parenteser. Då måste vi bevisa att också de enkla uttrycken (p + q) och (p²) har ett jämnt antal parenteser.

Först addition. Vi definierar också funktionen z(q), som ger antalet parenteser i uttrycket q. Då gäller att uttrycket (p + q) har z(p) + z(q) + 2 parenteser. Det har alltså två parenteser fler än summan av antalet parenteser i uttrycken p och q. Enligt antagandet är både z(p) och z(q) jämna, så om vi adderar tre jämna tal får vi återigen ett jämnt tal. I det här fallet gäller alltså påståendet.

Nu potensen. Återigen gäller antagandet att det enkla uttrycket p innehåller ett jämnt antal parenteser. Uttrycket (p²) innehåller då z(p) + 2 parenteser, alltså återigen två parenteser fler än uttrycket p. Också i det här fallet adderar vi jämna tal, så resultatet är jämnt.

Påståendet gäller för det första elementet och gäller också i induktionssteget, därför är påståendet sant.