1.6 Induksjonsbevis

Dominorekken som beviser alt

Se for deg en uendelig lang rekke dominobrikker, én for hvert naturlig tall. Du vil garantere at alle faller. Å dytte hver enkelt brikke er umulig — det er uendelig mange. Men du trenger bare å sikre to ting: at den første brikken faller, og at hver brikke som faller, velter den neste. Da faller brikke én, som velter brikke to, som velter brikke tre — og dominoeffekten ruller gjennom hele uendeligheten.

Dette er nøyaktig tankegangen bak matematisk induksjon, en av de mektigste bevisteknikkene i matematikken. Mange formler — som at $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ — påstår noe om alle naturlige tall. Vi kan teste $n = 1$, $n = 5$ og $n = 1000$, men testing beviser aldri uendelig mange tilfeller. Induksjon gjør det, med et endelig argument i to steg. I dette kapittelet lærer du oppskriften og bruker den på summer, ulikheter og delelighet.

Oppskriften: basissteg og induksjonssteg

La $P(n)$ være påstanden vi vil bevise for alle $n \geq n_0$ (oftest $n_0 = 1$). Induksjonsbeviset har to deler:

1. Basissteg: Vis at $P(n_0)$ er sann — den første dominobrikken faller.

2. Induksjonssteg: Anta at $P(k)$ er sann for en vilkårlig $k$ (dette kalles induksjonshypotesen), og vis at da må $P(k+1)$ også være sann — hver fallende brikke velter den neste.

Er begge på plass, gjelder $P(n)$ for alle $n \geq n_0$.

La oss bevise klassikeren: $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$.

Basissteg ($n = 1$): venstre side er $1$, høyre side er $\displaystyle \frac{1 \cdot 2}{2} = 1$. Likt — brikke én faller.

Induksjonssteg: Anta $\displaystyle 1 + 2 + \cdots + k = \frac{k(k+1)}{2}$. Legg til neste ledd, $k+1$, på begge sider:

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

Men dette er nøyaktig formelen med $n = k+1$! Antakelsen om brikke $k$ veltet brikke $k+1$, og beviset er fullført. Legg merke til det avgjørende grepet: vi brukte induksjonshypotesen til å erstatte summen av de $k$ første leddene.

Induksjon på ulikheter og delelighet

Dominoeffekten virker på mer enn sumformler. La oss bevise ulikheten $2^n > n$ for alle $n \geq 1$.

Basissteg ($n = 1$): $2^1 = 2 > 1$. ✓

Induksjonssteg: Anta $2^k > k$. Da er

$$2^{k+1} = 2 \cdot 2^k > 2k = k + k \geq k + 1$$

siden $k \geq 1$. Altså er $2^{k+1} > k+1$, og dominoen ruller videre. Legg merke til teknikken: vi skrev $2^{k+1}$ som $2 \cdot 2^k$ nettopp for å få brukt hypotesen.

Induksjon behersker også delelighet. Påstand: $n^3 - n$ er delelig med $6$ for alle $n \geq 1$.

Basissteg: $1^3 - 1 = 0$, og $0$ er delelig med $6$. ✓

Induksjonssteg: Anta at $6$ deler $k^3 - k$. Vi regner ut differansen mellom neste og nåværende tilfelle:

$$(k+1)^3 - (k+1) = (k^3 - k) + 3k(k+1)$$

Første parentes er delelig med $6$ etter hypotesen. I andre ledd er $k(k+1)$ et produkt av to påfølgende heltall — alltid delelig med $2$ — så $3k(k+1)$ er delelig med $6$. Summen av to tall delelige med $6$ er selv delelig med $6$. ✓

Tre helt ulike påstander, samme maskineri. Det er induksjonens styrke: ett prinsipp, utallige anvendelser.

Oppsummering: dominoeffekten som bevismetode

Matematisk induksjon løser et umulig-utseende problem — å bevise noe for uendelig mange tall — med to endelige steg. Basissteget dytter den første dominobrikken: vis at $P(n_0)$ er sann. Induksjonssteget sikrer kjedereaksjonen: anta $P(k)$ (induksjonshypotesen) og vis at den tvinger frem $P(k+1)$. Sammen gir de $P(n)$ for alle $n \geq n_0$.

Vi har sett maskineriet håndtere tre ulike typer påstander: sumformelen $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$, der vi la til neste ledd og omformet; ulikheten $2^n > n$, der omskrivingen $2^{k+1} = 2 \cdot 2^k$ åpnet døren for hypotesen; og deleligheten $6 \mid n^3 - n$, der differansen $(k+1)^3 - (k+1) = (k^3 - k) + 3k(k+1)$ gjorde jobben. Husk fellene: formuler $P(n)$ presist, hopp aldri over basissteget — uten startbrikke faller ingenting — og sørg for at induksjonshypotesen faktisk brukes i induksjonssteget. Med dette har du et verktøy som bærer langt utover R2: induksjon er ryggraden i bevis gjennom hele matematikken og informatikken.