Induktionsbevis

I Matte 5-kursen lärde vi oss om induktionsbevis. I många logiska system formuleras induktionsprincipen som ett axiom, medan det i andra system går att härleda induktionsprincipen. I det här avsnittet kommer vi först gå igenom en informell förklaring för induktionsbevis, sedan en formell definition och slutligen ger vi ett exempel på ett induktionsbevis.

Informell förklaring

Eftersom induktionsprincipen handlar om påståenden som har att göra med naturliga tal större än eller lika med ett startvärde (till exempel 0, 1 eller 2), kan induktionsprincipen visualiseras med hjälp av dominobrickor. Att bevisa någonting med induktion sker i 3 steg.

1. Visa att påståendet är sant för ett startvärde, till exempel \(n=1\)
2. Antag att påståendet är sant för något heltal \(n\)
3. Visa, med hjälp antagandet i steg 2, att påståendet är sant för heltalet \(n+1\)

Visualiseringen med hjälp av dominorbrickor går ut på att vi radar upp ett antal dominobrickor på högkant. Principen innebär att om en bricka välter, kommer nästkommande bricka också att välta. Detta betyder att om den första brickan välter, välter alla brickor. Det är viktigt att notera att steg 1 måste ingå, för det är här vi visar att den första dominobrickan verkligen välter.

Formell defintion

I avsnittet Vad är logik? lärde vi oss några vanligt förekommande symboler som används inom logiken. Nu kommer vi använda dessa för att definiera induktionsprincipen.

Antag att ett påstående \(P(n)\) är sant för något naturligt tal \(n\). Om

• \(P(1)\) är sant, och
• \(\forall x\in\mathbb{N}:P(x)\implies P(x+1)\)

så är \(P(n)\) sant för alla positiva heltal \(n\). 

Den andra punkten ovan utläsen "för alla \(x\) som ligger i de naturliga talen så gäller att \(P(x)\) implicerar \(P(x+1)\)". Jämför detta med dominobrickorna, om en bricka faller kommer nästa bricka också att falla.

Antagandet som definitionen börjar med kan tolkas som steg 2 i den informella definitionen, första punkten som steg 1 och andra punkten som steg 3.

Exempel på induktionsbevis

Sats: Summan av de \(n\) första kvadraterna är \(k_n=\dfrac{n(n+1)(2n+1)}{6}\).

Satsen ovan säger att \(1^2+2^2+3^2+\dots+n^2=\dfrac{n(n+1)(2n+1)}{6}\).

Bevis med induktion: Vi börjar med steg 1, det såkallade bassteget.

För \(n=1\) får vi:

$$k_1=1^2=1=\frac{1(1+1)(2\cdot 1+1)}{6}=\frac{1\cdot 2\cdot 3}{6}=\frac{6}{6}=1$$

Alltså stämmer formeln för \(n=1\).

Steg 2: Antag att formeln stämmer för något \(n>1\).

Steg 3: Vi vill nu visa, med hjälp av antagandet i steg 2, att formeln gäller för \(n+1\), det vill säga att

$$k_{n+1}=\frac{(n+1)(n+2)(2n+3)}{6}$$

Eftersom antagandet i steg 2 säger

$$k_n=1^2+2^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}$$

kan vi lägga till \((n+1)^2\) på båda sidor och vi får

$$k_{n+1}=(1^2+2^2+\dots+n^2)+(n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2$$

Om vi nu lyckas visa att 

$$\frac{(n+1)(n+2)(2n+3)}{6}=\frac{n(n+1)(2n+1)}{6}+(n+1)^2$$

är vi klara. Vi börjar med att förkorta med \((n+1)\) på båda sidor.

$$\frac{(n+2)(2n+3)}{6}=\frac{n(2n+1)}{6}+(n+1)$$

Nu förlänger vi båda sidor med 6 och får

$$\begin{align}(n+2)(2n+3)&=n(2n+1)+6(n+1)\\&\iff\\2n^2+7n+6&=2n^2+n+6n+6\\&\iff\\2n^2+7n+6&=2n^2+7n+6\end{align}$$

Eftersom \(VL=HL\) har vi bevisat satsen!