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 pastander for alle naturlige tall ved a bruke et endelig argument. Tenk på dominobrikker: hvis den forste 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}

Basisteg ( $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)$ ! ✓

📝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$ .

Basisteg ( $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$ )

Altsa $2^{k+1} > k + 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$ .

Basisteg ( $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 (indukhyp)
- $k(k+1)$ er delelig med 2 (to pafolgende tall)
- Dermed er $3k(k+1)$ delelig med 6

Summen er delelig med 6. ✓

📝Oppgave 3

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

Oppsummering

Tips for induksjonsbevis:
- Formuler pastanden $P(n)$ klart
- Sjekk alltid basisteget forst
- Bruk induksjonshypotesen eksplisitt
- Vis tydelig hvordan du far $P(k+1)$ fra $P(k)$

Repetisjonsoppgaver

Din fremgang

0deloppgaver0 / 5 oppgaver