6.2 Matematisk induksjon: strukturen og de fire undertypene

Et induksjonsbevis har nøyaktig tre merkede deler. Alle tre skal stå, hver gang.

(1) Basissteg. Verifisér $P(n_0)$ med tall. Ikke «det er klart for $n=1$» — regn ut begge sider og se at de er like.

(2) Induksjonshypotese. Skriv som egen linje: «Anta at $P(k)$ holder for en $k\ge n_0$», og skriv ut hva $P(k)$ er.

(3) Induksjonssteg. Utled $P(k+1)$, med setningen «Her bruker vi induksjonshypotesen:» plassert nøyaktig der du bruker den.

Malen må sitte utenat. Under kode D finnes ingen mal å slå opp i, og de tre stegene er selve strukturen løsningsforslagene fører.

Hvert steg bærer uttelling for seg selv. Det betyr at et halvferdig induksjonsbevis med riktig struktur er verdt mer enn et ferdig svar uten den — og at et bevis uten basissteg mangler en tredjedel av det oppgaven ber om.

Avslutningssetningen: «Ved induksjonsprinsippet holder $P(n)$ for alle $n\ge n_0$.» Den er ikke pynt: den sier at du har brukt prinsippet, og at du vet at de to punktene til sammen er nok.

Merk hva som IKKE hører i et induksjonsbevis: en tabell over noen verdier. Sjekker du $n=1,2,3,4$ i basissteget, har du gjort fire basissteg og trenger fortsatt bare ett. Bruk tiden på steget i stedet.

Verifikasjonen av $P(n_0)$ — det ene tilfellet du regner ut direkte.

Slik føres det:

«Basissteg ($n=n_0$): venstre side er $\dots$, høyre side er $\dots$. De er like, så $P(n_0)$ holder.»

Begge sider skal regnes ut. Det er hele poenget: du viser at kjeden har et startpunkt som faktisk er sant.

Et induksjonsbevis uten basissteg er en byggefeil, og det er den best belagte feilen i arkivets bevisdel. Grunnen er ikke formalisme — den er at steget alene beviser ingenting, som eksempel 5 viser med en falsk påstand der steget går perfekt.

Hvilket $n_0$? Det oppgaven sier. Står det «for alle $n\ge 1$», er $n_0=1$. Står det «for alle $n\ge 5$», er $n_0=5$, og du skal regne ut $n=5$ — ikke $n=1$.

Når $n_0$ ikke er oppgitt (typisk i ulikheter: «finn den minste $n_0$ slik at …»), skal du prøve deg frem og skrive at du gjorde det: «For $n=1,2,3$ er påstanden falsk; for $n=4$ er den sann. Vi tar $n_0=4$.» Det er en del av svaret.

Flere basissteg? Ja, når rekursjonen ser mer enn ett ledd tilbake. Bruker steget både $P(k)$ og $P(k-1)$, må to startverdier verifiseres — se sterk induksjon i løkke 5.

Antakelsen «$P(k)$ holder for en $k\ge n_0$», skrevet som egen linje med innholdet utskrevet.

Slik føres det:

«Induksjonshypotese: anta at det for en $k\ge n_0$ gjelder at $\underbrace{1+2+\dots+k=\tfrac{k(k+1)}2}_{P(k)}$.»

Skriv ut hva $P(k)$ er. «Anta at påstanden holder for $k$» er halvveis; likningen skal stå, for det er den du skal sette inn om et øyeblikk.

Ordet «en $k$» er viktig. Du antar ikke at det gjelder for alle $k$ (det ville vært det du skal vise). Du antar det for én, vilkårlig, fast $k$ — og viser at det da også gjelder for $k+1$.

Hvorfor det ikke er sirkelbevis: du beviser implikasjonen «$P(k)\Rightarrow P(k+1)$». Å anta $P(k)$ inne i et bevis for en implikasjon er nøyaktig hva man skal gjøre — det er samme grep som «anta $P$» i et direkte bevis (kap. 6.1).

Den vanligste feilen her er å ikke bruke hypotesen i det hele tatt. Kommer du gjennom steget uten å ha satt inn $P(k)$ noe sted, har du enten funnet et direkte bevis (som er fint, men da skal du si det) eller gjort en feil. Kontrollen: pek på linjen der hypotesen ble brukt. Finnes den ikke, er det ikke induksjon.

Utledningen av $P(k+1)$ fra $P(k)$ — den delen som er faglig arbeid.

Slik føres det:

«Induksjonssteg: vi skal vise $P(k+1)$, altså at $\dots$. Start fra venstre side:
[regn frem til noe som inneholder $P(k)$-uttrykket]
Her bruker vi induksjonshypotesen: [sett inn]
[regn videre til høyre side av $P(k+1)$]
Altså holder $P(k+1)$.»

Setningen «Her bruker vi induksjonshypotesen:» må sitte utenat, og den skal stå nøyaktig der innsettingen skjer. Fasitene i arkivet markerer alltid dette stedet, og det er den enkleste måten å vise at beviset faktisk er et induksjonsbevis.

Arbeidsretningen: begynn i den enden som inneholder $P(k)$. For summeformler er det venstre side ($S(k+1)=S(k)+a_{k+1}$). For delelighet er det uttrykket $f(k+1)$, som skal skrives om til $f(k)$ pluss noe. For ulikheter starter du med den minste siden og bruker hypotesen som en ulikhet.

Skriv ned hva $P(k+1)$ er, før du begynner. Å ha målet på papiret er halve arbeidet — ellers regner du i blinde.

Den andre vanlige feilen: å regne på begge sider samtidig til man ender på «$0=0$». Det er sirkelbevis-formen fra kap. 6.1 med mindre hvert steg er en ekvivalens. Den trygge formen er å starte i én ende og regne til den andre.

Slik føres hvert induksjonsbevis i boka, og slik bør du føre det på eksamen. Malen er identisk i kap. 6.4, i prøvene og i øvingseksamenene.

(i) Basissteg. $P(n_0)$ verifisert med tall — begge sider regnet ut, og riktig $n_0$.

(ii) Induksjonshypotese. «Anta at $P(k)$ holder for en $k\ge n_0$», satt opp som egen linje, med innholdet utskrevet.

(iii) Induksjonssteg. Utled $P(k+1)$, med setningen «Her bruker vi induksjonshypotesen:» plassert nøyaktig der den brukes.

Avslutning: «Ved induksjonsprinsippet holder $P(n)$ for alle $n\ge n_0$. $\blacksquare$»

Malen må sitte utenat, og hvert av de tre stegene bærer uttelling for seg selv. Grunnen er instruksen som står på hvert eneste sett: alle svar må begrunnes — og i et bevis er strukturen begrunnelsen.

Legg til kontrollen. Sett inn $n=n_0+1$ i den ferdige formelen og regn ut begge sider direkte. Stemmer de, har du fanget de fleste regnefeil; stemmer de ikke, er det formelen eller steget som er galt, og du vet hvor du skal se.

Grepet i steget, som må sitte utenat:
$$S(k+1)=S(k)+a_{k+1}.$$
Du skiller ut det siste leddet, bytter $S(k)$ med $F(k)$ fra hypotesen, og regner $F(k)+a_{k+1}$ om til $F(k+1)$.

Arbeidsflyten i fire trinn:

1. Skriv ned målet $F(k+1)$ først, med $k+1$ satt inn og forenklet.
2. Skriv $S(k+1)=S(k)+a_{k+1}$, med $a_{k+1}$ regnet ut eksplisitt.
3. Sett inn hypotesen.
4. Regn $F(k)+a_{k+1}$ frem til $F(k+1)$ — og det er her algebraen ligger.

Trinn 1 er det som sparer mest tid. Vet du hva du skal frem til, ser du hvilken faktorisering du trenger. Uten målet regner du i blinde.

Det vanligste algebra-grepet: sett den felles faktoren utenfor. I eksempel 1 var det $(k+1)^2$; i sumformelen for $\sum i^2$ er det $\displaystyle \frac{k+1}{6}$. Se etter faktoren $k+1$ i begge leddene — den er der nesten alltid.

Formlene du kan møte, og som du kan utlede hvis de glipper:

$$\sum_{i=1}^n i=\frac{n(n+1)}2,\qquad \sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}6,\qquad \sum_{i=1}^n i^3=\left(\frac{n(n+1)}2\right)^2.$$

Den første utledes på stedet, to linjer (Gauss-trikset): skriv summen forlengs og baklengs under hverandre,
$$\begin{aligned}S&=1+2+\dots+n\\ S&=n+(n-1)+\dots+1\end{aligned}$$
og legg sammen kolonnevis: hver kolonne gir $n+1$, og det er $n$ kolonner, så $2S=n(n+1)$. Under et minutt, så formelen kan gjenskapes selv om den skulle glippe.

Grepet i steget, som må sitte utenat:
$$f(k+1)=f(k)+\underbrace{R}_{\text{åpenbart delelig med }d}.$$
Er begge leddene delelige med $d$ — det første etter hypotesen, det andre fordi du ser det — er summen det.

Arbeidsflyten i fem trinn:

1. Regn ut $f(k+1)$.
2. Let etter $f(k)$ inni uttrykket. Det ligger der, ofte skjult bak en faktor.
3. Skriv $f(k+1)=A\cdot f(k)+R$, der $A$ er et helt tall.
4. Her bruker vi induksjonshypotesen: $f(k)=d\cdot t$.
5. Vis at $R$ er delelig med $d$, og faktoriser $d$ ut av helheten.

Trinn 2 er der oppgaven avgjøres, og trikset er å regne baklengs: hva må du gange $f(k)$ med for å nærme deg $f(k+1)$?

Eksempel på grepet, uten hele beviset: skal du vise $7\mid 8^n-1$, er
$$8^{k+1}-1=8\cdot 8^k-1=8(8^k-1)+7,$$
altså $f(k+1)=8f(k)+7$. Begge leddene er delelige med $7$ — det første etter hypotesen, det andre fordi det er $7$.

Alternativ som ofte er kortere: skriv $f(k+1)-f(k)$ og vis at differansen er delelig med $d$. Det er samme regning, snudd, og noen fasiter fører den slik. Begge er fullgode.

Merk at delelighetspåstander ofte kan vises uten induksjon — med case-analyse (kap. 6.1), med kongruensregning (kap. 1.4) eller med Fermats lille teorem (kap. 2.2). Ber oppgaven om induksjon, fører du induksjon; ber den bare om et bevis, velger du selv.

Tallet $n_0$ der påstanden begynner å gjelde. Det er ikke alltid $1$, og i ulikheter er det nesten aldri $1$.

Hvordan du finner den — utledes på stedet, under et minutt: prøv $n=1,2,3,\dots$ til påstanden blir sann. Men pass på to feller:

1. Påstanden kan være sann for små $n$ og så bli falsk igjen, før den blir sann for godt. Da er $n_0$ det stedet der den blir sann og forblir det — og induksjonssteget er det som garanterer «forblir».
2. Likhet er ikke ulikhet. For $2^n>n^2$ gir $n=4$ at $16>16$ er falsk. Da er $n_0=5$, ikke $4$.

Hva som skal stå i besvarelsen: «For $n=1,2,3,4$ er påstanden falsk (verdiene er $\dots$); for $n=5$ er den sann. Vi tar $n_0=5$.» Prøvingen er en del av svaret, ikke forarbeid du kan skjule.

Basissteget bruker $n_0$, ikke $1$. Skriver du «basissteg $n=1$» i en oppgave med $n_0=5$, har du verifisert noe som er galt — og det er en umiddelbar feil.

Merk at induksjonssteget kan kreve $k\ge$ noe. I ulikhetsbevis trenger du ofte at $k$ er stor nok for at en mellomulikhet holder (typisk $k^2\ge 2k+1$, som krever $k\ge 3$). Skriv betingelsen når du bruker den, og sjekk at den er oppfylt for alle $k\ge n_0$.

Grepet i steget: du kan ikke regne deg fra venstre til høyre med likhetstegn. I stedet lager du en kjede av ulikheter, der hypotesen er ett av leddene:
$$A(k+1)\ \ge\ (\text{noe med }A(k))\ \overset{\text{hypotese}}{>}\ (\text{noe med }B(k))\ \ge\ B(k+1).$$

Arbeidsflyten i fem trinn:

1. Finn $n_0$ ved å prøve, og skriv hva du fant.
2. Basissteg med $n_0$, begge sider regnet ut.
3. Hypotese: $A(k)>B(k)$ for en $k\ge n_0$.
4. Steg: uttrykk $A(k+1)$ ved $A(k)$ (typisk $A(k+1)=2A(k)$ eller $A(k+1)=(k+1)A(k)$), bruk hypotesen, og vis at det du får, er $\ge B(k+1)$.
5. Den siste ulikheten er ofte en egen liten påstand — «$2k^2\ge(k+1)^2$ for $k\ge 3$». Vis den, ikke bare påstå den.

Trinn 5 er der ulikhetsoppgaver skiller seg fra de andre undertypene. Du får en restulikhet som må vises for seg, og den vises typisk ved å gange ut og se at differansen er positiv.

Retningen på ulikhetene må holdes. Ganger du med et negativt tall, snur ulikheten — men i disse oppgavene er alt positivt, så det er sjelden et problem. Verre er å blande $>$ og $\ge$: er hypotesen streng, er konklusjonen streng, og du skal skrive den riktige.

Grepet: induksjonen går på grunntallet $a$, ikke på eksponenten, når påstanden er $a^p\equiv a\pmod p$. Steget bruker binomialformelen og resultatet $p\mid\binom pk$ for $1\le k\le p-1$ (kap. 2.2, fullt bevist i kap. 6.3):

$$(a+1)^p=\sum_{k=0}^p\binom pk a^k=a^p+\underbrace{\binom p1 a^{p-1}+\dots+\binom p{p-1}a}_{\text{alle ledd delelige med }p}+1.$$

Modulo $p$ faller mellomleddene bort, så
$$(a+1)^p\equiv a^p+1\pmod p.$$

Her bruker vi induksjonshypotesen $a^p\equiv a$:
$$(a+1)^p\equiv a+1\pmod p,$$
som er påstanden for $a+1$. Med basissteget $a=1$ ($1^p=1\equiv 1$) er beviset ferdig.

Dette er ett av to fullgode bevis for samme resultat. Det andre er Fermats lille teorem (kap. 2.2): for $p\nmid a$ er $a^{p-1}\equiv 1$, og gang med $a$; for $p\mid a$ er begge sider $\equiv 0$. Si hvilken vei du bruker. Induksjonsveien er den oppgaven ber om når den sier «vis ved induksjon», og den er dessuten den som ikke forutsetter Fermat.

Kongruensmønstre i følger følger vanlig induksjon, ofte sterk: er $u_{n+1}=u_n+u_{n-1}$, ser steget to ledd tilbake, og da trenger du to basissteg. Se neste kort.

Merk at kongruensregning gjør induksjonsteget kort. Å arbeide modulo $p$ i stedet for med hele tall sparer deg for å holde orden på et delelig restledd — kongruensspråket fra kap. 1.4 er verktøyet som gjør denne undertypen håndterlig.

En utvidet hypotese: i stedet for å anta bare $P(k)$, antar du $P(j)$ for alle $j$ med $n_0\le j\le k$.

Malen:

(1) Basissteg: verifisér $P(n_0)$ — og $P(n_0+1)$, $P(n_0+2)$, … så mange som rekursjonen ser tilbake.
(2) Induksjonshypotese (sterk): anta at $P(j)$ holder for alle $j$ med $n_0\le j\le k$.
(3) Induksjonssteg: utled $P(k+1)$, med bruk av de tidligere tilfellene du trenger — og si hvilke.

Når du trenger den: når $P(k+1)$ avhenger av mer enn ett tidligere tilfelle. To typiske situasjoner:

1. Rekursjoner som ser to ledd tilbake: $u_{k+1}=3u_k-2u_{k-1}$. Steget bruker både $P(k)$ og $P(k-1)$, så basissteget må dekke to startverdier.
2. Påstander der du deler et tall i to mindre faktorer: «hvert $n\ge 2$ er et produkt av primtall» — steget skriver $n=ab$ med $a,b<n$ og bruker hypotesen på begge, som kan ligge hvor som helst under $n$.

Antall basissteg = antall ledd rekursjonen ser tilbake. Det er regelen, og den er den vanligste feilen i sterk induksjon: ett basissteg der to var nødvendig. Kontrollen: se på steget og tell hvilke tidligere tilfeller du bruker. Bruker du $P(k)$ og $P(k-1)$, må steget virke fra $k=n_0+1$, og da må $P(n_0)$ og $P(n_0+1)$ begge være verifisert direkte.

Sterk induksjon er ikke sterkere enn vanlig induksjon i logisk forstand — begge følger av velordningsprinsippet, og du kan oversette mellom dem. Men den er ofte mye bekvemmere, og fasitene bruker den der rekursjonen krever det.