Induksjonsbevis

Induksjon er en effektiv teknikk for å bevise en påstand som gjelder for naturlige tall. I videoen blir det gitt en forklaring og et eksempel blir gjennomgått.

MatRIC: Induksjonsbevis

Rettighetshaver: MatRIC ved Universitetet i Agder / MatRIC

Begreper

Implikasjon

En påstand $P$ impliserer en annen påstand $Q$ hvis det følger at $Q$ er sann hvis $P$ er sann. Vi skriver $P \Rightarrow Q$ .

Eksempel: "Alle i klassen har gul t-skjorte" impliserer "Ingen i klassen har grønn t-skjorte".

Implikasjon

Matematisk induksjon

En metode til å bevise en påstand P(n) der det inngår et positivt heltall n. Følgende to skritt må gjennomføres:

Bevis påstanden for n =1.
Bevis at for ethvert positivt tall k vil man fra hypotesen P(k) kunne slutte at hypotesen også gjelder for P(k+1).

Siden vi vet fra 1. at hypotesen gjelder for P(1) kan vi ved hjelp av 2. slutte at den også gjelder for P(2). Fra dette kan vi slutte at den også må gjelde for P(3), og så videre for alle P(n).

Matematisk induksjon

Oppgaver

1. Gjør eksempelet i videoen. Forsøk uten hjelpemidler. Står du fast kan du følge trinnene i videoen.

LØSNING

Se video.

2. Bruk induksjonsbevis til å vise at for alle $n \in ℕ$ er

$\sum_{i = 1}^{n} i^{2} = \frac{1}{6} n (n + 1) (2 n + 1)$ .

LØSNING

Trinn 1:

Sjekker for $n = 1$ :
venstre side $= 1^{2} = 1 = \frac{1}{6} \cdot 1 \cdot (1 + 1) (2 \cdot 1 + 1) =$ høyre side

Trinn 2:

Antar sant for $n = k$ : $\sum_{i = 1}^{k} i^{2} = \frac{1}{6} k (k + 1) (2 k + 1)$ .

Viser nå for $n = k + 1$ :
venstre side
$= \sum_{i = 1}^{k + 1} i^{2}$
$= \sum_{i = 1}^{k} i^{2} + (k + 1)^{2}$
(nå brukes induksjonshypotesen)
$= \frac{1}{6} k (k + 1) (2 k + 1) + (k + 1)^{2}$
$= \frac{1}{6} (k + 1) (k (2 k + 1) + 6 (k + 1))$
$= \frac{1}{6} (k + 1) (2 k^{2} + k + 6 k + 6)$
$= \frac{1}{6} (k + 1) ((k + 2) (2 k + 3))$
$= \frac{1}{6} (k + 1) ((k + 1) + 1) (2 (k + 1) + 1)$
$=$ høyre side

$□$

3. Bruk induksjonsbevis til å vise at for alle

n \in ℕ

1 + 2 + 4 + 8 + . . . + 2^{n - 1} = 2^{n} - 1

LØSNING

Trinn 1:

Sjekker for $n = 1$ :
venstre side $= 2^{0} = 1 = 2^{1} - 1 =$ høyre side

Trinn 2:

Antar sant for $n = k$ : $1 + 2 + 4 + 8 + . . . + 2^{k - 1} = 2^{k} - 1$ .

Viser nå for $n = k + 1$ :
venstre side
$= 1 + 2 + 4 + 8 + . . . + 2^{k}$
$= 1 + 2 + 4 + 8 + . . . + 2^{k - 1} + 2^{k}$
(nå brukes induksjonshypotesen)
$= (2^{k} - 1) + 2^{k}$
$= 2 (2^{k}) - 1$
$= 2^{k + 1} - 1$
$=$ høyre side

$□$

Del på Facebook

Del på Facebook

Matematikk for studenter

Bevisteknikk

Består av:

Induksjonsbevis