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 ei uendeleg rad med dominobrikker. Viss du veit at:
1. Den første brikka veltar
2. Kvar gong ei brikke veltar, veltar ho òg den neste

Då veit du at alle brikkene veltar.

Dette er ideen bak matematisk induksjon -- ein bevismetode for påstandar som gjeld for alle naturlege tal $n \geq n_0$ . Metoden er særleg nyttig for å bevise formlar for summar, delelegheit og ulikskapar.

Prinsippet for matematisk induksjon

P(n)

Basissteget gjev oss $P(n_0)$ .

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

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

Slik held vi fram og når kvart naturleg tal $n \geq n_0$ .

✏️Eksempel 1: Summen av dei $n$ første naturlege tala

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

Induksjonsantaking: Anta at formelen gjeld 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 gjeld formelen for alle $n \geq 1$ . $\square$

Vanlege feil ved induksjon

1. Gløymer basissteget: Utan basissteg har beviset inga forankring. Ein kan "bevise" usanne påstandar.

2. Sirkelargument: I induksjonssteget må du vise $P(k) \Rightarrow P(k+1)$ . Du må bruke $P(k)$ som ei antaking og utleie $P(k+1)$ , ikkje anta $P(k+1)$ direkte.

3. Feil retning: Start med den sida du veit noko om (som inneheld $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 kvadrattal

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øgre side: $\displaystyle \frac{1 \cdot 2 \cdot 3}{6} = 1$ . $\checkmark$

Induksjonsantaking: $\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 delelegheit

Induksjon er òg eit kraftig verktøy for å bevise at visse uttrykk alltid er delelege med eit bestemt tal. Strategien er å skrive $P(k+1)$ ved hjelp av $P(k)$ og vise at delelegheitskravet er oppfylt.

✏️Eksempel 3: Delelegheit med 6

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

Bevis ved induksjon:

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

Induksjonsantaking: $k^3 - k$ er deleleg med $6$ , dvs. $k^3 - k = 6m$ for eit heiltal $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 deleleg med $6$ (induksjonsantakinga). For andre ledd: $k(k+1)$ er produktet av to påfølgjande heiltal, så det er alltid partal. Altså er $3k(k+1)$ deleleg med $6$ .

Summen av to tal delelege med $6$ er deleleg med $6$ . $\square$

📝Oppgave 3

Vis ved induksjon at $3^n - 1$ er deleleg 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 ulikskapar

Induksjon kan òg brukast til å bevise ulikskapar. Framgangsmaaten er den same, men i induksjonssteget brukar vi ofte at $P(k)$ gjev ei nedre (eller øvre) skranke som vi kan byggje vidare på.

✏️Eksempel 4: Bernoullis ulikskap

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$ . Likskap gjeld. $\checkmark$

Induksjonsantaking: $(1+x)^k \geq 1 + kx$ for ein $k \geq 1$ .

Induksjonssteg:

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

der vi brukte antakinga og at $(1+x) \geq 0$ (sidan $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 ulikskap gjeld 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 ein bevismetode for påstandar $P(n)$ som gjeld 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)$

Vanlege bruksområde:
- Summeformlar: $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$
- Delelegheit: " $n^3 - n$ er deleleg med $6$ "
- Ulikskapar: " $2^n > n$ " (Bernoullis ulikskap)

Tips:
- Skriv alltid induksjonsantakinga tydeleg
- I induksjonssteget: start med venstre side for $k+1$ og bruk antakinga
- Marker tydeleg kvar induksjonsantakinga vert brukt
- Hugs at induksjonsantakinga ikkje er "sirkelbevis" -- ho er ei betinga antaking 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.