Side 1 av 1

Induksjonsbevis: trinn 1

Lagt inn: 06/05-2019 20:45
av Banan
Hei

Jeg repeterer til eksamen og merker at jeg har glemt en del, kan noen hjelpe:

Dersom man har fått oppgave å bevise S(n)= (3n^2-n)/2 og a(n)= 3n-2

på trinn 1, skal man vise at formelen gjelder for n=1 på S(n) eller a(n)?

Jeg så på to eksempel oppgaver og så at den ene viser trinn I på a(n) og den andre på S(n), hva er riktig?

Takk

Re: Induksjonsbevis: trinn 1

Lagt inn: 06/05-2019 23:09
av Nebuchadnezzar
Begge ;)

Hypotesen vi ønsker å teste er at

$ \hspace{1cm}
a(1) + a(2) + \cdots a(n-1) + a(n) = S(n) \qquad (1)
$

Målet er å vise at høyre side (HS) og venstre side av likningen ovenfor er sann for ALLE heltall $n$ større enn null.

Så første steget er å sjekke om HS = VS når $n = 1$. Ved å sette inn på hver side får vi

HS: $a(1) = 3\cdot 1 - 2 = 1$ og VS: $S(1) = (3 \cdot 1^2- 1)/2 = 1$

Så utsagnet stemmer for $n = 1$. Vi trenger ikke, men dersom vi skulle ha testet om likning 1 stemte for $n = 2$ ville vi testet om

HS: $a(1) + a(2)$ og VS: $S(2)$

var like. Merk at vi aldri sammenlikner disse direkte fordi vi ikke enda vet at de er like, så å skrive $a(1) + a(2) = S(2)$ blir feil måte å sjekke at de er like på.

================

Steg 2

Her antar vi at likning 1 holder for et SPESIFIKT heltall $k \geq 1$,

$ \hspace{1cm}
a(1) + a(2) + \cdots + a(k-1) + a(k) = S(n)
$

Dette kalles for induksjonshypotesen.
Vi ønsker å vise at dette medfører (altså må vi bruke likningen jeg nettop skrev, til å vise den under) at

$ \hspace{1cm}
a(1) + a(2) + \cdots +a(k) + a(k +1) = S(k+1) \qquad \quad (2)
$

Merk igjen at for å være helt formelle vet vi ikke at likningen over stemmer, og vi burde ikke bruke den. Heller burde vi gjøre som før å vise at VS = HS.

HS: $S(k + 1) = \ldots$

VS: $\bigr[ a(1) + a(2) + \cdots +a(k) \bigl] + a(k +1) = S(k) + a(k+1) = \cdots$

Her overlater jeg det til deg å fylle inn $\cdots$ til du ser at VS og HS er like. Merk at i første overgang brukte jeg induksjonshypotesen (likning 2). Dette er samme fremgangsmåte for de fleste slike oppgaver :p

Re: Induksjonsbevis: trinn 1

Lagt inn: 07/05-2019 21:00
av Banan
Nebuchadnezzar skrev:Begge ;)

Hypotesen vi ønsker å teste er at

$ \hspace{1cm}
a(1) + a(2) + \cdots a(n-1) + a(n) = S(n) \qquad (1)
$

Målet er å vise at høyre side (HS) og venstre side av likningen ovenfor er sann for ALLE heltall $n$ større enn null.

Så første steget er å sjekke om HS = VS når $n = 1$. Ved å sette inn på hver side får vi

HS: $a(1) = 3\cdot 1 - 2 = 1$ og VS: $S(1) = (3 \cdot 1^2- 1)/2 = 1$

Så utsagnet stemmer for $n = 1$. Vi trenger ikke, men dersom vi skulle ha testet om likning 1 stemte for $n = 2$ ville vi testet om

HS: $a(1) + a(2)$ og VS: $S(2)$

var like. Merk at vi aldri sammenlikner disse direkte fordi vi ikke enda vet at de er like, så å skrive $a(1) + a(2) = S(2)$ blir feil måte å sjekke at de er like på.

================

Steg 2

Her antar vi at likning 1 holder for et SPESIFIKT heltall $k \geq 1$,

$ \hspace{1cm}
a(1) + a(2) + \cdots + a(k-1) + a(k) = S(n)
$

Dette kalles for induksjonshypotesen.
Vi ønsker å vise at dette medfører (altså må vi bruke likningen jeg nettop skrev, til å vise den under) at

$ \hspace{1cm}
a(1) + a(2) + \cdots +a(k) + a(k +1) = S(k+1) \qquad \quad (2)
$

Merk igjen at for å være helt formelle vet vi ikke at likningen over stemmer, og vi burde ikke bruke den. Heller burde vi gjøre som før å vise at VS = HS.

HS: $S(k + 1) = \ldots$

VS: $\bigr[ a(1) + a(2) + \cdots +a(k) \bigl] + a(k +1) = S(k) + a(k+1) = \cdots$

Her overlater jeg det til deg å fylle inn $\cdots$ til du ser at VS og HS er like. Merk at i første overgang brukte jeg induksjonshypotesen (likning 2). Dette er samme fremgangsmåte for de fleste slike oppgaver :p

Tusen takk, lol.