9.2 Induksjon

Dominoeffekten

Se for deg en uendelig rad med dominobrikker. Du vet to ting: den første brikken velter, og hver brikke som velter, dytter over den neste. Trenger du å sjekke brikke nummer 1 000 000 for å vite at den faller? Nei – de to opplysningene garanterer at alle brikkene faller, hele den uendelige raden.

Dette er ideen bak matematisk induksjon, bevismetoden for påstander som skal gjelde for alle naturlige tall: «formelen stemmer for alle $n \geq 1$», «uttrykket er delelig med 6 for alle $n$», «ulikheten holder for alle $n$». Slike påstander har uendelig mange tilfeller – umulig å sjekke ett og ett. Men induksjonen trenger bare to steg: vis at det første tilfellet stemmer (den første brikken velter), og vis at hvert tilfelle dytter over det neste.

I dette kapittelet lærer du metodens faste struktur – basissteg, induksjonsantagelse og induksjonssteg – og bruker den på de tre klassiske områdene: summeformler, delelighet og ulikheter.

Prinsippet – to steg mot uendeligheten

Slik formuleres metoden presist. For å bevise at en påstand $P(n)$ gjelder for alle heltall $n \geq n_0$, viser vi to ting. Basissteget: $P(n_0)$ er sann – det første tilfellet sjekkes direkte. Induksjonssteget: hvis $P(k)$ er sann for et vilkårlig $k \geq n_0$ – dette kalles induksjonsantagelsen – så er også $P(k+1)$ sann. Da følger det at $P(n)$ gjelder for alle $n \geq n_0$.

Hvorfor virker dette? Følg kjeden: basissteget gir $P(n_0)$. Induksjonssteget anvendt med $k = n_0$ gir $P(n_0+1)$. Anvendt igjen med $k = n_0+1$ gir det $P(n_0+2)$. Og slik fortsetter det – ethvert naturlig tall nås til slutt av kjeden, akkurat som enhver dominobrikke i raden til slutt blir truffet.

Et punkt forvirrer mange: «antar vi ikke det vi skal bevise?» Nei – og forskjellen er subtil, men avgjørende. Vi antar ikke at $P(k)$ er sann for alle $k$; vi viser implikasjonen $P(k) \Rightarrow P(k+1)$: hvis en gitt brikke velter, så velter den neste. Implikasjonen alene beviser ingenting – det er kombinasjonen med basissteget som setter kjeden i gang. Derfor er begge stegene uunnværlige: uten basissteg har du en perfekt rekke brikker som ingen har dyttet; uten induksjonssteg har du én veltet brikke og stillstand.

Summeformler – induksjonens paradegren

La oss bevise den berømte formelen $\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ for alle $n \geq 1$.

Basissteg ($n = 1$): venstre side er $1$, høyre side er $\displaystyle \frac{1 \cdot 2}{2} = 1$. Stemmer.

Induksjonsantagelse: anta at $\displaystyle 1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ for et vilkårlig $k \geq 1$.

Induksjonssteg: vi skal vise formelen for $n = k+1$. Start med venstre side og bruk antagelsen på de første $k$ leddene:

$$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}$$

Og dette er nøyaktig formelen med $n = k+1$. Ved induksjonsprinsippet gjelder formelen for alle $n \geq 1$. $\square$

Legg merke til selve manøveren i induksjonssteget – den er alltid den samme for summer: splitt av det siste leddet, bruk antagelsen på resten, og rydd algebraen til målformen. Samme oppskrift beviser formelen for kvadratsummene, $\displaystyle 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$: basissteget gir $\displaystyle 1 = \frac{1 \cdot 2 \cdot 3}{6}$, og i induksjonssteget legger man $(k+1)^2$ til antagelsen og faktoriserer seg fram til $\displaystyle \frac{(k+1)(k+2)(2k+3)}{6}$.

De vanligste feilene? Å glemme basissteget (uten forankring kan man «bevise» rene usannheter), å anta $P(k+1)$ i stedet for å utlede den, og å regne fra feil ende. Start alltid med den siden som inneholder $P(k)$-strukturen, og marker tydelig hvor antagelsen brukes.

Delelighet og ulikheter – induksjonens andre arenaer

Induksjon beviser mer enn formler. Delelighet først: påstanden er at $n^3 - n$ er delelig med 6 for alle $n \geq 1$.

Basissteget: $1^3 - 1 = 0 = 6 \cdot 0$. Greit nok. Induksjonsantagelsen: $k^3 - k = 6m$ for et heltall $m$. I induksjonssteget skriver vi uttrykket for $k+1$ slik at antagelsen kommer til syne:

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

Første ledd er delelig med 6 per antagelse. Andre ledd: $k(k+1)$ er et produkt av to påfølgende heltall og dermed alltid partall, så $3k(k+1)$ er delelig med $3 \cdot 2 = 6$. Summen av to 6-delelige tall er 6-delelig. $\square$ Strategien: manipuler $P(k+1)$-uttrykket til «$P(k)$-delen pluss en rest», og vis at resten oppfyller kravet.

Så ulikheter, med Bernoullis ulikhet som kronstykke: $(1+x)^n \geq 1 + nx$ for alle $n \geq 1$ og $x \geq -1$.

Basissteget ($n=1$): $(1+x)^1 = 1 + x$ – likhet. Induksjonssteget: anta $(1+x)^k \geq 1 + kx$. Gang begge sider med $(1+x)$ – som er $\geq 0$ nettopp fordi $x \geq -1$, så ulikheten bevares:

$$(1+x)^{k+1} \geq (1+kx)(1+x) = 1 + (k+1)x + kx^2 \geq 1 + (k+1)x$$

der siste skritt bruker at $kx^2 \geq 0$. $\square$ Merk de to stedene betingelsene jobbet: $x \geq -1$ sikret at vi kunne multiplisere uten å snu ulikheten, og kvadratleddet kunne trygt kastes fordi det aldri er negativt. I ulikhetsbevis er det ofte nettopp slike små observasjoner som bærer hele induksjonssteget.

Oppsummering: uendelig mange tilfeller, to steg

Matematisk induksjon beviser påstander $P(n)$ for alle $n \geq n_0$ med dominologikk: basissteget sjekker $P(n_0)$ direkte – det første dyttet – og induksjonssteget viser implikasjonen $P(k) \Rightarrow P(k+1)$ – at hver brikke velter den neste. Induksjonsantagelsen er ikke sirkelresonnement, men premisset i en implikasjon; det er kombinasjonen med basissteget som setter den uendelige kjeden i bevegelse.

De tre store arenaene fikk hver sin teknikk. Summeformler som $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$: splitt av siste ledd, bruk antagelsen, rydd til målformen. Delelighet som «$6 \mid n^3 - n$»: skriv $P(k+1)$-uttrykket som antagelsens del pluss en rest, og vis at resten duger – her ved at $k(k+1)$ alltid er partall. Ulikheter som Bernoullis $(1+x)^n \geq 1 + nx$: multipliser antagelsen forsiktig (sjekk fortegn!) og kast ikke-negative ledd.

Og husk feilene som feller flest: glem aldri basissteget, anta aldri $P(k+1)$, og marker alltid tydelig hvor antagelsen brukes. I neste kapittel fullfører vi bevisverktøykassen med de indirekte metodene – kontrapositiv og kontradiksjon.