1.6 Induksjonsbevis | Matematikk R2

Matematisk induksjon

Hvordan kan vi bevise at en formel gjelder for alle naturlige tall? Vi kan ikke sjekke uendelig mange tilfeller.

Matematisk induksjon lar oss bevise påstander for alle naturlige tall ved å bruke et endelig argument. Tenk på dominobrikker: hvis den første faller og hver brikke velter den neste, faller alle.

Matematisk induksjon

P(n)

✏️Eksempel 1: Sumformel

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

P(n)

\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}

Basissteg ( $n = 1$ ):
VS: $1$ , HS: $\displaystyle \frac{1 \cdot 2}{2} = 1$ ✓

Induksjonssteg:
Anta $P(k)$ : $\displaystyle 1 + 2 + \cdots + k = \frac{k(k+1)}{2}$

Vis $P(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 $P(k+1)$ . ✓

Ved induksjon gjelder formelen for alle $n \geq 1$ .

📝Oppgave 1

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

✏️Eksempel 2: Ulikhet

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

Basissteg ( $n = 1$ ):

2^1 = 2 > 1

✓

Induksjonssteg:
Anta $2^k > k$ .

$2^{k+1} = 2 \cdot 2^k > 2k \geq k + 1$
(siden $k \geq 1$ )

Altså $2^{k+1} > k + 1$ ✓

Ved induksjon gjelder $2^n > n$ for alle $n \geq 1$ .

📝Oppgave 2

Bevis ved induksjon at $n! > 2^n$ for alle $n \geq 4$ .

✏️Eksempel 3: Delelighet

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

Basissteg ( $n = 1$ ):

1^3 - 1 = 0

, og

6 | 0

✓

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

- $(k^3 - k)$ er delelig med 6 (induksjonshypotesen)
- $k(k+1)$ er delelig med 2 (to påfølgende tall)
- Dermed er $3k(k+1)$ delelig med 6

Summen er delelig med 6. ✓

Ved induksjon er $n^3 - n$ delelig med 6 for alle $n \geq 1$ .

📝Oppgave 3

Bevis at $4^n - 1$ er delelig med 3 for alle $n \geq 1$ .

Oppsummering

Tips for induksjonsbevis:
- Formuler påstanden $P(n)$ klart
- Sjekk alltid basissteget først
- Bruk induksjonshypotesen eksplisitt
- Vis tydelig hvordan du får $P(k+1)$ fra $P(k)$

Repetisjonsoppgaver

Din fremgang

0deloppgaver0 / 5 oppgaver