Regel: Induksjon#
Forutsetninger og læringsmål#
Matematisk induksjon er en regel for direkte argumentasjon. Den bygger i praksis på forståelse av både argumentasjon, variable og likninger. Vår framstilling skal også bygge på innsetting: Vi forutsetter at \(n ↦ k\) betyr “n får verdien k” eller “k settes inn for n”.
Målet er at du skal kunne
bygge induksjonsbevis
undervise om induksjonsbevis
Referanser:
Introduksjon#
Matematisk induksjon er en av de reglene som ofte blir opplevd vanskelig.
Et induktivt bevis har en konkusjon (eller påstand) som skal bevises for alle tilfeller i et (induksjons-)rom (eller induksjonsmengde). I mange av våre tilfeller er induksjonsrommet rett og slett ℕ (rommet av naturlige tall). Rommet må ha et startpunkt.
Et induktivt bevis for at en påstand gjelder for alle tilfeller i rommet må inneholde
et grunnsteg (eller basissteg): Et bevis for at konklusjonen holder for det første tilfellet i rommet.
et induksjonssteg: Et bevis for at om konklusjonen holder for et tilfelle holder det også for det neste.
et bevis for at induksjonssteget spenner over alle tilfeller i rommet. Om rommet er ℕ (de naturlige tall / telletallene) er dette ofte enkelt (og blir noen ganger glemt).
Eksempler#
Flere eksempler på Wikipedia om matematisk induksjon.
Induksjon over ℕ: \(n² ≥ n\)#
Konklusjon: Vi ønsker å bevise at \(n² ≥ n\) for alle \(n∈ℕ\).
Induksjonsrommet: ℕ
Grunnsteg: Dette stemmer opplagt om vi setter inn 1 for \(n\) (altså \(n ↦ 1\)): \(1² ≥ 1\).
Induksjonssteg: Vi ønsker å bevise at
om vi forutsetter formelen sånn den ser ut med \(k\) (altså \(n ↦ k\); dette blir \(k² ≥ k\))
kan vi bevise formelen sånn den ser ut med \(k+1\) (altså \(n ↦ k+1\); dette blir \((k+1)² ≥ k+1\))
Dette beviser vi med denne argumentasjonen:
\(k² ≥ k\)
\(⇔ k² + 1 ≥ k + 1\) (legger til 1 på hver side)
\(⇒ k² + 2k + 1 ≥ k + 1\) (vi forutsetter at \(2k > 0\), og kan legge til på venstre side)
\(⇔ (k + 1)² ≥ k + 1\) (faktoriserer) (Det var dette vi skulle bevise)
Bevis for at induksjonssteget spenner ut induksjonsrommet: Induksjonssteget går fra enhver \(k ≥ 1\) til \(k+1\), og spenner dermed ut alle hele positive tall.
Representasjoner#
Navn#
Fig. 1.54 Induksjonsplatetopp (elektromagnetisk induksjon)#
Ordet induksjon brukes dessverre om forskjellige ting:
Matematisk induksjon, som i denne artikkelen
Naturvitenskapelig induksjon, som er noe helt annet. Naturvitenskapelig induksjon er å gå fra mange spesifikke eksempler til noe generelt. Dette tilsvarer eksempelbevis.
Elektromagnetisk induksjon: Magnetfelt lager strøm (for eksempel for matlaging)
Ordforklaring: Induksjon
In-duksjon betyr inn-ledning. Duksjon (ledning) har vi også i ord som aquadukt (vannledning), viadukt (veiledning/bro), duktil (formbart), reduksjon (om-ledning), deduksjon (avledning), produsere (fram-lede) og seduce (vekk-lede).
Tegning#
Induksjonsrom har en bestemt “form”: Man starter et sted og bygger seg utover. I det vanligste tilfellet beveger man seg utover i en rekke. Er induksjonsrommet ℕ, starter man gjerne på 0 eller 1. Dette kan tegnes for eksempel som en rekke dominoklosser.
Ord#
Vi ønsker å bevise en påstand / konklusjon for alle tilfeller i (induksjons)rommet/-mengden.
Til det bruker vi
et grunnsteg/basissisteg/induksjonsgrunnlag/…
et induksjonssteg/induksjonsskritt/induksjonsledd/…
Formelspråket#
Induksjonsrom: La oss her si at induksjonsrommet er ℕ; dette kan skiftes ut med ℚ eller en annen mengde.
Påstand: La oss si at vi skal bevise \(P\) for alle \(n ∈ ℕ\). Dette kan vi skrive med formelen \(∀n ∈ ℕ : P(n)\). I stedet for \(P(n)\) kan man også skrive \(P_n\).
Grunnsteget blir da \(P(1)\).
Induksjonssteget blir \(P(k) ⇒ P(k+1)\). Dette kan også skrives \(P\{n ↦ k\} ⇒ P\{n↦k+1\}\) (hvor tegnet ↦ står for innsetting).
Som en regel kan vi si \(\overset{grunnsteg ~ ∧ ~ induksjonssteg}{\underset{konklusjon}{↓}}\), altså \(\overset{P\{n ↦ 1\} ~ ∧~ P\{n~ ↦ k\}~ ⇒ ~P \{n~↦k + 1\}}{\underset{∀n ∈ ℕ ~ P(n)}{↓}}\)
Task#
Algoritmer#
Lese bevis#
Når man skal lese bevis kan man passe på:
Er det virkelig noen argumentasjon for at induksjonssteget spenner hele induksjonsrommet, eller er dette bare underforstått?
Forstår du virkelig strukturen i induksjonssteget? Det finnes en god del oppset Ellef synes er vanskelig å forstå. Noen argumenterer for eksempel for at \(P(k) = P(k+1)\); dette kan være forvirrende; noen setter opp det som egentlig er en argumentasjon for \(P(k+1) ⇒ P(k)\) (feil vei).
Bevise#
Å bevise er ofte vanskeligere enn å forstå et bevis, akkurat som det er vanskeligere å skrive god musikk eller å glede seg over god musikk. Her er noen punkt som kan taes i bruk:
Formulere påstand og induksjonsrom#
Først bør man formulere hva man ønsker å bevise, og hvilken mengde det spenner over. Er mengden ℕ? Kanskje ℕ₀ (naturlige tall og 0)? De fleste av eksemplene i 5MA302 er over ℕ.
Det er ikke alltid helt opplagt hva man ønsker å bevise. Videre vil vi kalle vår påstand P, eller P(n) for tilfellet n.
Dette kan gjerne formuleres som en formel, men det kan også formuleres med ord eller andre representasjonsspråk.
Bevise grunnsteg#
Grunnsteget er altså P(1) eller liknende. Dette er oftest enkelt å bevise. Man kan bare sette 1 inn for n i P (altså \(P\{n↦1\}\)).
Bevise induksjonssteg#
Dette er typisk mye vanskeligere.
Induksjonssteget er typisk \(P(k) ⇒ P(k + 1)\). Først bør man formulere tydelig hva \(P(k)\) og \(P(k+1)\) er.
Så kan man forsøke å lage en utregning fra \(P(k)\) til \(P(k+1)\). I argumentasjonen kan man bruke alt man vet (f.eks. at \(k > 0\)).
Implikasjonen / argumentasjonen går “ovenfra og nedover” fra \(P(k)\) til \(P(k+1)\); men det er vanlig at det er enklere å finne argumentasjonen ved å jobbe “nedenfra og oppover” fra konklusjonen. Som vanlig går altså prosessen litt annen vei enn argumentasjonen vi skal finne.
Et annet triks er å bruke eksempler: Om man først beviser \(P(1)\), \(P(2)\) og kanskje \(P(2) ⇒ P(3)\) får man kanskje idéer til hvordan man kan bevise \(P(k) ⇒ P(k+1)\).
Bevise at induksjonssteget spenner induksjonsrommet#
Om induksjonsrommet er ℕ, grunnsteget er for {n ↦ 1} og induksjonssteget går fra {n ↦ k} til {n ↦ k+1} er dette nesten selvfølgelig.
Ofte blir dette dessverre nesten glemt.
Andre induksjonsrom#
De fleste ekempler vi snakker om har induksjonsrommet ℕ. Det går også an å ha andre induksjonsrom, f.eks. ℚ (rasjonale tall / brøktall), inkludere negative tall, trestrukturer etc.
Oppgave: Bevis at alle årstall med moderne Olympiske leker er delelig med 4
Løsningsforslag
Her er mengden ikke ℕ, men derimot en del tall fra 1896 (Athen) og framover. Vi kan bruke 1896 som grunnsteg; dette er delelig på 4.
Induksjonssteget er “hvis årstallet for et OL er delelig på 4, er årstallet for neste OL også delelig på 4”. La oss kalle årstallet for et OL for k; da er neste årstall med OL k+4. Vi må altså argumentere for at 4|k ⇒ 4|k+1. Dette kan f.eks. gjøres ved å se på de to siste sifrene (slik kan vi jo avgjøre om et tall er delelig på 4). Dette kan selvsagt settes opp svært detaljert, f.eks. ved å faktorisere, men det er ikke poenget her.
Så må vi argumentere for at dette induksjonssteget spenner over alle moderne Olympiske leker. Dette må nesten gjøres med kulturell kunnskap (og å glemme forstyrrelser som verdenskriger, Covid-19 og forskyving av vinter-OL).
Det samme kunne også vært bevist ved uttømming.
Eksempel: Induksjon over en trestruktur: Fra Adam#
Påstand: Vi ønsker å bevise at alle menn har et Y-kromosom.
Induksjonsmengde: Alle menn.
Grunnsteg: Vi forutsetter at Adam hadde et Y-kromosom.
Induksjonsseg: Vi forutsetter at om en mann har et y-kromosom vil også hans sønner arve et y-kromosom.
Induksjonssteget spenner alle tilfeller: Vi forutsetter at alle menn nedstammer fra Adam.
Dette eksempelet viser at induksjon også kan være over andre strukturer enn ℕ, tilmed trestrukturer.
Vi ser også at induksjonsargument, som alle argument, er avhengig av visse forutsetninger som kan diskuteres ☺.
Vi kunne også laget et liknende argument for X-kromosom for alle mennesker; da kunne vi begynt med to startpunkt: Adam og Eva.
Rekursive definisjoner#
Induksjonsbevis passer godt med rekursive definisjoner, f.eks. aritmetiske rekker, geometriske rekker, … Et annet ord på rekursive definisjoner er induktive definisjoner.
oppgaver
Definer en aritmetisk rekke rekursivt, og bevis en formel for summen av de n første leddene.
Definer en geometrisk rekke rekursivt, og bevis en formel for summen av de n første leddene.
Hvor mange forforeldre vil en person ha i ledd nr. \(n\)? (f.eks. vil en person ha fire besteforeldre, i ledd 2). Finn en formel og bevis.
Oppgaver#
Induksjonsbevis#
\(\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\, \qquad \forall n \in \mathbb{N}\)#
Først bør man forstå godt hva som egentlig påstås. \(\sum_{i=1}^{n}i\) betyr “Summen av i fra 1 til n”. Et eksempel er bra: Setter man {n ↦ 3} får vi \(\sum_{i=1}^{3}i=\frac{3(3+1)}{2} = 6\), altså \(1 + 2 + 3 = 6\). Vi snakker om summen av de \(n\) første naturlige tallene.
Løsningsforslag
Induksjonsrommet er ℕ.
Grunnsteget kan være {n ↦ 1}: Da får vi at summen av det første tallet er \(\frac{1(1+1)}{2}\); dette er sant.
Induksjonssteget er at \(\sum_{i=1}^{k}i=\frac{k(k+1)}{2}\) impliserer \(\sum_{i=1}^{k+1}i=\frac{(k+1)(k+1+1)}{2}\). Det beviser vi med utregningen
\(\sum_{i=1}^{k}i=\frac{k(k+1)}{2}\)
\(⇔ \sum_{i=1}^{k}i + (k+1) =\frac{k(k+1)}{2} + (k + 1)\) Legger til på begge sider
\(⇔ \sum_{i=1}^{k+1}i =\frac{k(k+1)}{2} + (k + 1)\) Summen av de k første tallene + (k+1) = summen av de k+1 første tallene
\(⇔ \sum_{i=1}^{k+1}i =\frac{k² + k}{2} + \frac{2k + 2}{2}\)
\(⇔ \sum_{i=1}^{k+1}i =\frac{(k+1)(k+2)}{2}\) Som var det vi skulle bevise.
Igjen: Denne utregningen er kanskje enklest å finne “nedenfra og opp”.
Grunnsteget beviser tilfellet 1. Induksjonssteget går fra \(k\) til \(k+1\); dermed er alle tilfeller i induksjonsrommet ℕ dekket.
\(1^2 + 2^2 + 3^2 +.....+ n^2 = \frac{n(n+1)(2n+1)}{6} \qquad n \in \mathbb{N}\)#
Løsningsforslag hos matematikk.net eksempel 2
Bevis at \(n^3 - 4n + 6\) er delelig på 3 når n er et ikke-negativt heltall#
Løsningsforslag
Induksjonsrommet er ℕ₀ (altså med 0).
Grunnsteget kan alstå være {n ↦ 0}. Dette gir \(0^3 - 4n + 6 → 6\) som er delelig på 3.
Induksjonstrinnet er altså en utregning fra \(3|k^3 - 4k + 6\) til \(3|(k+1)^3 - 4(k+1) + 6\) (tegnet | betyr “er faktor i”).
\(3|k^3 - 4k + 6\)
\(⇔ 3|k^3 - 4k + 6 + 3(k² + k - 1)\) Legger på noe som er klart delelig på 3
\(⇔ 3|k^3 + 3k² + 3k - 3 - 4k + 6\)
\(⇔ 3|k^3 + 2k² + k + k^2 + 2k + 1 - 4k-4 + 6\)
\(⇔ 3|(k^3 + 2k² + k) + (k^2 + 2k + 1) - 4k-4 + 6\)
\(⇔ 3|(k+1)(k^2 + 2k + 1) - 4k-4 + 6\)
\(⇔ 3|(k+1)(k+1)^2 - 4k-4 + 6\)
\(⇔ 3|(k+1)^3 - 4(k+1) + 6\) Som skulle bevises
Også dette lages enklest nedenfra.
Oppgaver fra NDLA#
Læring#
Induksjon er ansett for å være vanskelig. Jeg finner disse poengene nyttige:
n og k#
Skill mellom n i påstanden og k i induksjonssteget.
TODO
Dette har matematisk begrunnelse:
n er variabelen som er i “for alle”; den betyr at påstanden gjelder for alle n ∈ ℕ.
k er variabelen i dette induksjonssteget; det er en “mer lokal” verdi.
Om vi skulle si ting som \(n = n + 1\) vil elevene bli forvirret, med god grunn. Dette er jo et utsagn som aldri kan være sant! Og \(n = n\) er alltid sant. Vi bør si \(n = k + 1\) (eller helst \(n ↦ k+1\), se under).
Hvorfor ↦#
Bruk notasjon for innsetting, f.eks. ↦, heller enn likhetstegn.
TODO
Vi snakker jo ikke egentlig om en likhet, men om en innsetting (eller “settes lik”).