Matematisk induktion

Kurs: M0065M Förkunskaper: Logik och bevisföring

---

Matematisk induktion är ett sätt att bevisa att en utsaga gäller för oändligt många heltal genom att bara göra två ändliga kontroller. Den används framför allt för summaformler, olikheter och delbarhet, och för rekursivt definierade talföljder.

Idén — dominobrickor

Ställ upp dominobrickor i en oändlig rad. Om den första brickan faller, och varje bricka som faller fäller nästa, så faller alla. Basfallet är den första brickan, induktionssteget är att varje bricka fäller nästa.

---

1. Induktionsprincipen

För att bevisa att en utsaga $P(n)$ gäller för alla heltal $n\ge n_0$:

1. Basfall: visa $P(n_0)$.
2. Induktionssteg: antag $P(k)$ och visa $P(k+1)$.

Då gäller $P(n)$ för alla $n\ge n_0$.

Antagandet att $P(k)$ är sann kallas induktionsantagandet. Vi antar det bara för ett godtyckligt $k\ge n_0$; det är implikationen $P(k)\Rightarrow P(k+1)$ som bevisas, inte $P(k)$ självt.

Summan $1+2+\cdots +n=n(n+1)/2$

Basfall ($n=1$): $1=1\cdot 2/2$. ✓ Induktionssteg: antag likheten för $n=k$. Då

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

---

2. Så skriver vi ett induktionsbevis för en summa

1. Formulera $P(p+1)$ genom att sätta $n=p+1$ i påståendet. Då vet vi exakt vilket uttryck vi ska nå fram till.
2. Dela upp summan i de $p$ första termerna och den sista:

$$\sum _{k=1}^{p+1}{a}_k=\left(\sum _{k=1}^p{a}_k\right)+a_{p+1}.$$

3. Använd induktionsantagandet på parentesen, och markera var det sker.
4. Förenkla tills vi får högerledet i $P(p+1)$. Ofta är det enklast att visa att $\text{VL}(p+1)-\text{HL}(p+1)=0$.

För olikheter fungerar samma schema, men i steg 4 behöver vi i regel en extra olikhet som håller för $p\ge n_0$. Det är där basfallet $n_0$ kommer in.

Föreläsning 30, exempel 5 — Olikheten $2^n>n^2$

Vi visar att $2^n>n^2$ för $n=5,6,7,\dots$

Lösning

Basfall ($n=5$): $2^5=32>25=5^2$. ✓

Induktionsantagande. Antag att $2^p>p^2$ för något $p\ge 5$.

Induktionssteg. Vi vill visa $2^{p+1}>(p+1{)}^2$. Med induktionsantagandet är

$$2^{p+1}=2\cdot 2^p>2p^2,$$

så det räcker att visa $2p^2\ge (p+1{)}^2$. Det är ekvivalent med

$$2p^2>p^2+2p+1⟺p^2-2p-1>0⟺(p-1{)}^2>2,$$

som är sant eftersom $p-1\ge 4$.

Slutsats. Enligt induktionsaxiomet gäller $\boxed{2^n>n^2\text{ fo¨r alla }n\ge 5}$. Olikheten är falsk för $n=3$ och $n=4$ ($8<9$, $16=16$), så basfallet kan inte flyttas ner.

Stämmer med det handskrivna lösningsförslaget.

Vanliga fel

• Hoppa över basfallet. Induktionssteget ensamt bevisar ingenting: utsagan ${\sum }_{k=1}^n(2k-1)=n^2+5$ klarar induktionssteget men är falsk för varje $n$ (se Övningsuppgift 2.10 nedan).
• Anta det som ska visas. Vi får anta $P(p)$, inte $P(p+1)$. Att utgå från likheten för $p+1$ och härleda något sant, till exempel $0=0$, bevisar ingenting om inte varje steg är en ekvivalens. Räkna i stället på $\text{VL}(p+1)$ tills det blir $\text{HL}(p+1)$.
• Fel basfall för olikheter. Basfallet ska vara det minsta $n$ påståendet gäller för, och extraolikheten i steget måste hålla för alla $p$ från just det $n_0$.
• Otydligt var antagandet används. Markera steget där induktionsantagandet sätts in; utan det syns inte att beviset är ett induktionsbevis.

---

3. Lösta övningar

Testuppgift 2.8 b — En teleskoperande summa

Vi visar med induktion att, för alla positiva heltal $n$,

$$\sum _{k=1}^n\frac{1}{k(k+1)}=1-\frac{1}{n+1}.$$

Lösning

Basfall ($n=1$): $\text{VL}=\frac{1}{1\cdot 2}=\frac{1}{2}$ och $\text{HL}=1-\frac{1}{2}=\frac{1}{2}$. ✓

Induktionsantagande. $\sum _{k=1}^p\frac{1}{k(k+1)}=1-\frac{1}{p+1}$.

Induktionssteg. Vi ska nå $1-\frac{1}{p+2}$.

$$\sum _{k=1}^{p+1}\frac{1}{k(k+1)}\stackrel{\text{ind.ant.}}{=}1-\frac{1}{p+1}+\frac{1}{(p+1)(p+2)}=1-\frac{(p+2)-1}{(p+1)(p+2)}=1-\frac{1}{p+2}.$$

Slutsats. Formeln gäller för alla $n\ge 1$.

Resonemangsuppgift — det finns inget facit att jämföra med.

Övningsuppgift 2.9 e — Summa med $k\cdot 2^{-k}$

Vi visar med induktion att, för alla heltal $n\ge 1$,

$$\sum _{k=1}^{n}k\cdot 2^{-k}=2-(n+2)\cdot 2^{-n}.$$

Lösning

Basfall ($n=1$): $\text{VL}=\frac{1}{2}$ och $\text{HL}=2-3\cdot \frac{1}{2}=\frac{1}{2}$. ✓

Induktionsantagande. $\sum _{k=1}^{p}k\cdot 2^{-k}=2-(p+2)2^{-p}$.

Induktionssteg. Vi ska nå $2-(p+3)2^{-(p+1)}$. Skriv $2^{-p}=2\cdot 2^{-(p+1)}$:

$$\sum _{k=1}^{p+1}k\cdot 2^{-k}\stackrel{\text{ind.ant.}}{=}2-(p+2)2^{-p}+(p+1)2^{-(p+1)}=2-2^{-(p+1)}(2p+4-p-1)=2-(p+3)2^{-(p+1)}.$$

Slutsats. Formeln gäller för alla $n\ge 1$.

Resonemangsuppgift — det finns inget facit att jämföra med.

Övningsuppgift 2.10 — Varför basfallet behövs

a) Vi visar att om utsagan $\sum _{k=1}^n(2k-1)=n^2+c$ gäller för $n=p$, så gäller den också för $n=p+1$. Är utsagan därmed sann för alla $n\ge 1$?

b) Vi bestämmer talet $c$ så att utsagan gäller för alla $n\ge 1$.

Lösning

a) Antag ${\sum }_{k=1}^p(2k-1)=p^2+c$. Då är

$$\sum _{k=1}^{p+1}(2k-1)=p^2+c+(2(p+1)-1)=p^2+2p+1+c=(p+1{)}^2+c.$$

Induktionssteget håller alltså för varje $c$. Men utsagan är inte bevisad: basfallet saknas, och $\boxed{\text{Nej}}$ — utan det kan steget “fälla” brickor som aldrig började falla.

b) Basfallet $n=1$ kräver $1=1+c$, alltså $\boxed{c=0}$. Med basfallet och steget i a) gäller då ${\sum }_{k=1}^n(2k-1)=n^2$ för alla $n\ge 1$.

Facit: a) Nej! Utsagan måste också visas vara sann för $n=1$. b) $c=0$.

Övningsuppgift 2.12 — En olikhet för $\sum 1/k^2$

Vi visar med induktion att

$$\sum _{k=1}^n\frac{1}{k^2}<2-\frac{1}{n}\text{fo¨r alla heltal }n\ge 2.$$

Lösning

Basfall ($n=2$): $\text{VL}=1+\frac{1}{4}=\frac{5}{4}$ och $\text{HL}=2-\frac{1}{2}=\frac{3}{2}$. Eftersom $\frac{5}{4}<\frac{3}{2}$ stämmer det. ✓

Induktionsantagande. $\sum _{k=1}^p\frac{1}{k^2}<2-\frac{1}{p}$ för något $p\ge 2$.

Induktionssteg. Vi ska visa $\sum _{k=1}^{p+1}\frac{1}{k^2}<2-\frac{1}{p+1}$. Med antagandet är

$$\sum _{k=1}^{p+1}\frac{1}{k^2}<2-\frac{1}{p}+\frac{1}{(p+1{)}^2},$$

så det räcker att högerledet är högst $2-\frac{1}{p+1}$. Differensen är

$$\left(2-\frac{1}{p}+\frac{1}{(p+1{)}^2}\right)-\left(2-\frac{1}{p+1}\right)=\frac{-(p+1{)}^2+p+p(p+1)}{p(p+1{)}^2}=-\frac{1}{p(p+1{)}^2}<0.$$

Slutsats. Olikheten gäller för alla $n\ge 2$. Som bonus följer att ${\sum }_{k=1}^{\infty }1/k^2\le 2$.

Resonemangsuppgift — det finns inget facit att jämföra med.

Se även

• Talföljder och summor
• Logik och bevisföring

Resurser

• 3Blue1Brown: Induction (proof by induction)