9.2 Induksjon

Dominoeffekten

Sjå for deg ei uendeleg rad med dominobrikker. Du veit to ting: den første brikka veltar, og kvar brikke som veltar, dyttar over den neste. Treng du å sjekke brikke nummer 1 000 000 for å vite at ho fell? Nei – dei to opplysningane garanterer at alle brikkene fell, heile den uendelege rada.

Dette er ideen bak matematisk induksjon, bevismetoden for påstandar som skal gjelde for alle naturlege tal: «formelen stemmer for alle $n \geq 1$», «uttrykket er deleleg med 6 for alle $n$», «ulikskapen held for alle $n$». Slike påstandar har uendeleg mange tilfelle – umogleg å sjekke eitt og eitt. Men induksjonen treng berre to steg: vis at det første tilfellet stemmer (den første brikka veltar), og vis at kvart tilfelle dyttar over det neste.

I dette kapittelet lærer du den faste strukturen til metoden – basissteg, induksjonsantaking og induksjonssteg – og brukar han på dei tre klassiske områda: summeformlar, delelegheit og ulikskapar.

Prinsippet – to steg mot uendelegheita

Slik vert metoden formulert presist. For å bevise at ein påstand $P(n)$ gjeld for alle heiltal $n \geq n_0$, viser vi to ting. Basissteget: $P(n_0)$ er sann – det første tilfellet vert sjekka direkte. Induksjonssteget: viss $P(k)$ er sann for ein vilkårleg $k \geq n_0$ – dette vert kalla induksjonsantakinga – så er òg $P(k+1)$ sann. Då følgjer det at $P(n)$ gjeld for alle $n \geq n_0$.

Kvifor verkar dette? Følg kjeda: basissteget gjev $P(n_0)$. Induksjonssteget brukt med $k = n_0$ gjev $P(n_0+1)$. Brukt att med $k = n_0+1$ gjev det $P(n_0+2)$. Og slik held det fram – kvart naturleg tal vert til slutt nådd av kjeda, akkurat som kvar dominobrikke i rada til slutt vert treft.

Eit punkt forvirrar mange: «antar vi ikkje det vi skal bevise?» Nei – og skilnaden er subtil, men avgjerande. Vi antar ikkje at $P(k)$ er sann for alle $k$; vi viser implikasjonen $P(k) \Rightarrow P(k+1)$: viss ei gjeven brikke veltar, så veltar den neste. Implikasjonen åleine beviser ingenting – det er kombinasjonen med basissteget som set kjeda i gang. Difor er begge stega uunnverlege: utan basissteg har du ei perfekt rekkje brikker som ingen har dytta; utan induksjonssteg har du éi velta brikke og stillstand.

Summeformlar – paradegreina til induksjonen

Lat 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øgre side er $\displaystyle \frac{1 \cdot 2}{2} = 1$. Stemmer.

Induksjonsantaking: anta at $\displaystyle 1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ for ein vilkårleg $k \geq 1$.

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

$$\begin{aligned} &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} \end{aligned}$$

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

Legg merke til sjølve manøveren i induksjonssteget – han er alltid den same for summar: splitt av det siste leddet, bruk antakinga på resten, og rydd algebraen til målforma. Same oppskrift beviser formelen for kvadratsummane, $\displaystyle 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$: basissteget gjev $\displaystyle 1 = \frac{1 \cdot 2 \cdot 3}{6}$, og i induksjonssteget legg ein $(k+1)^2$ til antakinga og faktoriserer seg fram til $\displaystyle \frac{(k+1)(k+2)(2k+3)}{6}$.

Dei vanlegaste feila? Å gløyme basissteget (utan forankring kan ein «bevise» reine usanningar), å anta $P(k+1)$ i staden for å utleie han, og å rekne frå feil ende. Start alltid med den sida som inneheld $P(k)$-strukturen, og marker tydeleg kvar antakinga vert brukt.

Delelegheit og ulikskapar – dei andre arenaene til induksjonen

Induksjon beviser meir enn formlar. Delelegheit først: påstanden er at $n^3 - n$ er deleleg med 6 for alle $n \geq 1$.

Basissteget: $1^3 - 1 = 0 = 6 \cdot 0$. Greitt nok. Induksjonsantakinga: $k^3 - k = 6m$ for eit heiltal $m$. I induksjonssteget skriv vi uttrykket for $k+1$ slik at antakinga kjem til syne:

$$\begin{aligned} &(k+1)^3 - (k+1) \\ = {}&k^3 + 3k^2 + 3k + 1 - k - 1 \\ = {}&(k^3 - k) + 3k(k+1) \end{aligned}$$

Første ledd er deleleg med 6 per antaking. Andre ledd: $k(k+1)$ er eit produkt av to påfølgjande heiltal og dermed alltid partal, så $3k(k+1)$ er deleleg med $3 \cdot 2 = 6$. Summen av to 6-delelege tal er 6-deleleg. $\square$ Strategien: manipuler $P(k+1)$-uttrykket til «$P(k)$-delen pluss ein rest», og vis at resten oppfyller kravet.

Så ulikskapar, med Bernoullis ulikskap 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$ – likskap. Induksjonssteget: anta $(1+x)^k \geq 1 + kx$. Gang begge sider med $(1+x)$ – som er $\geq 0$ nettopp fordi $x \geq -1$, så ulikskapen vert teken vare på:

$$\begin{aligned} (1+x)^{k+1} &\geq (1+kx)(1+x) \\ &= 1 + (k+1)x + kx^2 \\ &\geq 1 + (k+1)x \end{aligned}$$

der siste skritt brukar at $kx^2 \geq 0$. $\square$ Merk dei to stadene vilkåra arbeidde: $x \geq -1$ sikra at vi kunne multiplisere utan å snu ulikskapen, og kvadratleddet kunne trygt kastast fordi det aldri er negativt. I ulikskapsbevis er det ofte nettopp slike små observasjonar som ber heile induksjonssteget.

Oppsummering: uendeleg mange tilfelle, to steg

Matematisk induksjon beviser påstandar $P(n)$ for alle $n \geq n_0$ med dominologikk: basissteget sjekkar $P(n_0)$ direkte – det første dyttet – og induksjonssteget viser implikasjonen $P(k) \Rightarrow P(k+1)$ – at kvar brikke veltar den neste. Induksjonsantakinga er ikkje sirkelresonnement, men premisset i ein implikasjon; det er kombinasjonen med basissteget som set den uendelege kjeda i rørsle.

Dei tre store arenaene fekk kvar sin teknikk. Summeformlar som $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$: splitt av siste ledd, bruk antakinga, rydd til målforma. Delelegheit som «$6 \mid n^3 - n$»: skriv $P(k+1)$-uttrykket som delen til antakinga pluss ein rest, og vis at resten duger – her ved at $k(k+1)$ alltid er partal. Ulikskapar som Bernoullis $(1+x)^n \geq 1 + nx$: multipliser antakinga forsiktig (sjekk forteikn!) og kast ikkje-negative ledd.

Og hugs feila som feller flest: gløym aldri basissteget, anta aldri $P(k+1)$, og marker alltid tydeleg kvar antakinga vert brukt. I neste kapittel fullfører vi bevisverktøykassa med dei indirekte metodane – kontrapositiv og kontradiksjon.