9.2 Induksjon | Matematikk R1

Matematisk induksjon som bevismetode for påstander om naturlige tall.

55 min

11 oppgaver

Matematisk induksjonBasistegInduksjonsstegInduksjonsantagelse

Du leser den tradisjonelle versjonen

Din fremgang i kapitlet

0 / 11 oppgaver

Kapitlets plass i kurset

Bygger på

9.1Direkte bevis og moteksempler

Matematisk induksjon

Tenk deg en uendelig rad med dominobrikker. Hvis du vet at:
1. Den første brikken velter
2. Hver gang en brikke velter, velter den også den neste

Da vet du at alle brikkene velter.

Dette er ideen bak matematisk induksjon -- en bevismetode for påstander som gjelder for alle naturlige tall $n \geq n_0$ . Metoden er spesielt nyttig for å bevise formler for summer, delelighet og ulikheter.

Prinsippet for matematisk induksjon

P(n)

Basissteget gir oss $P(n_0)$ .

Induksjonssteget med $k = n_0$ gir oss $P(n_0) \Rightarrow P(n_0 + 1)$ , altså $P(n_0 + 1)$ .

Induksjonssteget med $k = n_0 + 1$ gir oss $P(n_0 + 1) \Rightarrow P(n_0 + 2)$ , altså $P(n_0 + 2)$ .

Slik fortsetter vi og når ethvert naturlig tall $n \geq n_0$ .

✏️Eksempel 1: Summen av de $n$ første naturlige tallene

Vis at $\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ for alle $n \geq 1$ .

Bevis ved induksjon:

Basissteg ( $n = 1$ ): Venstre side: $1$ . Høyre side: $\displaystyle \frac{1 \cdot 2}{2} = 1$ . Stemmer. $\checkmark$

Induksjonsantagelse: Anta at formelen gjelder for $n = k$ , dvs.:
$1 + 2 + \cdots + k = \frac{k(k+1)}{2}$

Induksjonssteg (vis for $n = k+1$ ):

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

Dette er formelen med $n = k + 1$ . $\checkmark$

Ved induksjonsprinsippet gjelder formelen for alle $n \geq 1$ . $\square$

Vanlige feil ved induksjon

1. Glemmer basissteget: Uten basissteg har beviset ingen forankring. Man kan "bevise" usanne påstander.

2. Sirkelargument: I induksjonssteget må du vise $P(k) \Rightarrow P(k+1)$ . Du må bruke $P(k)$ som en antagelse og utlede $P(k+1)$ , ikke anta $P(k+1)$ direkte.

3. Feil retning: Start med den siden du vet noe om (som inneholder $P(k)$ ), og omform til $P(k+1)$ .

📝Oppgave 1

Vis ved induksjon at $1 + 3 + 5 + \cdots + (2n-1) = n^2$ for alle $n \geq 1$ .

✏️Eksempel 2: Summen av kvadrattall

Vis at $\displaystyle 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$ for alle $n \geq 1$ .

Bevis ved induksjon:

Basissteg ( $n = 1$ ): Venstre side: $1$ . Høyre side: $\displaystyle \frac{1 \cdot 2 \cdot 3}{6} = 1$ . $\checkmark$

Induksjonsantagelse: $\displaystyle 1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}$ .

Induksjonssteg:

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

$= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} = \frac{(k+1)[k(2k+1) + 6(k+1)]}{6}$

$= \frac{(k+1)(2k^2 + 7k + 6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$

Dette er formelen med $n = k+1$ (sjekk: $(k+1)((k+1)+1)(2(k+1)+1)/6$ ). $\square$

📝Oppgave 2

Vis ved induksjon at $\displaystyle 1 + r + r^2 + \cdots + r^n = \frac{r^{n+1} - 1}{r - 1}$ for alle $n \geq 0$ og $r \neq 1$ .

Induksjon og delelighet

Induksjon er også et kraftig verktøy for å bevise at visse uttrykk alltid er delelige med et bestemt tall. Strategien er å skrive $P(k+1)$ ved hjelp av $P(k)$ og vise at delelighetskravet er oppfylt.

✏️Eksempel 3: Delelighet med 6

Vis at $n^3 - n$ er delelig med $6$ for alle $n \geq 1$ .

Bevis ved induksjon:

Basissteg ( $n = 1$ ): $1^3 - 1 = 0 = 6 \cdot 0$ . Delelig med $6$ . $\checkmark$

Induksjonsantagelse: $k^3 - k$ er delelig med $6$ , dvs. $k^3 - k = 6m$ for et heltall $m$ .

Induksjonssteg:

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

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

Første ledd er delelig med $6$ (induksjonsantagelsen). For andre ledd: $k(k+1)$ er produktet av to påfølgende heltall, så det er alltid partall. Altså er $3k(k+1)$ delelig med $6$ .

Summen av to tall delelige med $6$ er delelig med $6$ . $\square$

📝Oppgave 3

Vis ved induksjon at $3^n - 1$ er delelig med $2$ for alle $n \geq 1$ .

📝Oppgave 4

Vis ved induksjon at summen $\displaystyle \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1}$ for alle $n \geq 1$ .

Induksjon og ulikheter

Induksjon kan også brukes til å bevise ulikheter. Fremgangsmaaten er den samme, men i induksjonssteget bruker vi ofte at $P(k)$ gir en nedre (eller øvre) skranke som vi kan bygge videre på.

✏️Eksempel 4: Bernoullis ulikhet

Vis at $(1 + x)^n \geq 1 + nx$ for alle $n \geq 1$ og $x \geq -1$ .

Bevis ved induksjon over $n$ :

Basissteg ( $n = 1$ ): $(1+x)^1 = 1 + x = 1 + 1 \cdot x$ . Likhet gjelder. $\checkmark$

Induksjonsantagelse: $(1+x)^k \geq 1 + kx$ for et $k \geq 1$ .

Induksjonssteg:

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

der vi brukte antagelsen og at $(1+x) \geq 0$ (siden $x \geq -1$ ).

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

der siste ulikhet gjelder fordi $kx^2 \geq 0$ .

Altså $(1+x)^{k+1} \geq 1 + (k+1)x$ . $\square$

📝Oppgave 5

Vis ved induksjon at $2^n > n$ for alle $n \geq 1$ .

📝Oppgave 6

Vis ved induksjon at $n! \geq 2^{n-1}$ for alle $n \geq 1$ .

Oppsummering

Matematisk induksjon er en bevismetode for påstander $P(n)$ som gjelder for alle $n \geq n_0$ :

1. Basissteg: Vis at $P(n_0)$ er sann
2. Induksjonssteg: Vis at $P(k) \Rightarrow P(k+1)$

Vanlige bruksområder:
- Summeformler: $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$
- Delelighet: " $n^3 - n$ er delelig med $6$ "
- Ulikheter: " $2^n > n$ " (Bernoullis ulikhet)

Tips:
- Skriv alltid induksjonsantagelsen tydelig
- I induksjonssteget: start med venstre side for $k+1$ og bruk antagelsen
- Marker tydelig hvor induksjonsantagelsen brukes
- Husk at induksjonsantagelsen ikke er "sirkelbevis" -- den er en betinget antagelse i implikasjonen $P(k) \Rightarrow P(k+1)$

Repetisjonsoppgaver

Din fremgang

0deloppgaver0 / 5 oppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.