WEBVTT Kind: captions; language: nb-no NOTE Treffsikkerhet: 91% (HØY) 00:00:00.000 --> 00:00:07.400 I denne snutten skal vi snakke om induksjonsbevis, som er en måte å bevise påstander om naturlige tall, eller som er 00:00:07.400 --> 00:00:13.500 knyttet til naturlige tall. Under induksjonsprinsippet ligger det en veldig enkel observasjon 00:00:13.500 --> 00:00:19.800 som kan være grei å peke ut helt fra starten av. Det er at hvis jeg har tallinjen bortover her, så har jeg 00:00:19.800 --> 00:00:29.500 de hele tallene. Jeg begynner på 1 og ikke på 0 denne gangen. Så det er 1, 2, 3, 4 osv. Så er det slik at 00:00:29.500 --> 00:00:35.200 hvis jeg nå plukker ut et eller annet helt tall, uansett hvor stort det måtte være, borti her, 00:00:35.200 --> 00:00:42.200 kanskje noen milliarder stort. Så lenge det er et helt tall, er det slik at når jeg starter på 1 og teller, 00:00:42.200 --> 00:00:49.300 så til 2, så til 3, så til 4 osv. Hvis jeg bare fortsetter dette her lenge nok, så kommer jeg til det tallet der borte. 00:00:49.300 --> 00:00:53.600 Det er i grunn det prinsippet som ligger under induksjon. NOTE Treffsikkerhet: 91% (HØY) 00:00:53.600 --> 00:01:03.599 Men hva er så induksjon? Jo, induksjon handler om å bevise ting for alle naturlige tall. La meg starte med 00:01:03.599 --> 00:01:10.700 et lite eksempel. Når du lærer å derivere, så oppdager du kanskje et mønster ganske fort. Hvis du prøver å 00:01:10.700 --> 00:01:22.900 derivere potenser av x, så er det slik at når du deriverer x^2, så får du 2x. Når du deriverer x^3, så får du 3x^2. 00:01:22.900 --> 00:01:34.800 Når du deriverer x^4, så får du 4x^3. Så det ser ut til å være et mønster her. 00:01:34.800 --> 00:01:41.900 I hvert eneste tilfelle så ser det ut som den potensen her oppe kommer fram, 2-tallet kommer fram der, 00:01:41.900 --> 00:01:49.200 3-tallet kommer fram der, 4-tallet kommer frem her. Og så det slik at potensen til x blir en mindre. 00:01:49.200 --> 00:01:54.100 x^2 går til x, x^3 går til x^2, x^4 går til x^3. NOTE Treffsikkerhet: 88% (HØY) 00:01:54.100 --> 00:02:01.300 Så det ser nesten ut til å være et generelt mønster her, slik at hvis jeg tar x opphøyd i et eller annet tall k 00:02:01.300 --> 00:02:10.400 og deriverer det, så ser det ut som det kommer en k fram. Så får jeg en potens mindre, 00:02:10.400 --> 00:02:13.149 nemlig x^(k-1). NOTE Treffsikkerhet: 90% (HØY) 00:02:13.149 --> 00:02:20.300 Nå vet jo du fra videregående skole at dette faktisk er en formel som gjelder. Men hvis man ikke har 00:02:20.300 --> 00:02:26.600 kommet så langt, hvis man bare har observert dette mønsteret; hvordan skulle man da vise at noe slikt holdt 00:02:26.600 --> 00:02:31.950 for alle mulige naturlige tall? Det er det som er spørsmålet her. NOTE Treffsikkerhet: 92% (HØY) 00:02:31.950 --> 00:02:40.300 Det første man gjorde, hvis man ikke så med en gang hvordan man fikk til dette, det var kanskje å teste denne 00:02:40.300 --> 00:02:47.500 hypotesen litt mere. Kanskje for å regne ut hva ble (x^5)', hva blir (x^6)'. osv. 00:02:47.500 --> 00:02:51.800 Det ville delvis være for å teste hypotesen, men kanskje også for å se om det er noe mønster, om det er 00:02:51.800 --> 00:02:59.400 et system som gjør at vi får dette uttrykket. La oss teste litt videre. Hvis jeg nå prøver å regne ut 00:02:59.400 --> 00:03:08.300 (x^5)' uten å kjenne denne generelle regelen. Hva vil jeg da gjøre? En mulighet, siden jeg 00:03:08.300 --> 00:03:17.400 kjenner (x^4)', er å dele opp dette her som et produkt. Si at x^5, det er x^4 ganget med x. Så jeg kan derivere 00:03:17.400 --> 00:03:23.400 det produktet der isteden. Hvis det da bruker produktregelen for derivasjon, så skal jeg først 00:03:23.400 --> 00:03:31.200 derivere x^4, og den kjenner jeg allerede. Den er 4x^3. Da har jeg derivert den, 00:03:31.200 --> 00:03:32.300 og så skal jeg bare la den stå. NOTE Treffsikkerhet: 88% (HØY) 00:03:32.300 --> 00:03:39.700 Så jeg skal gange med x. Så får jeg en ny sum, hvor jeg skal la den første faktoren stå, x^4, og så skal jeg derivere x-en, 00:03:39.700 --> 00:03:47.300 som da bare er 1. Og så kan vi samle det sammen. Vi ser at vi har x^4 begge steder. 00:03:47.300 --> 00:03:57.800 De to kombinerer seg til x^4. Så jeg har 4x^4 her pluss en x^4 til der borte. Så jeg får 5x^4. NOTE Treffsikkerhet: 85% (HØY) 00:03:57.800 --> 00:04:04.200 Det stemmer jo med hypotesen vår. Når jeg deriverer x^5, så får jeg 5-tallet ned foran, og så får jeg 00:04:04.200 --> 00:04:07.150 en potens lavere, nemlig x^4. NOTE Treffsikkerhet: 91% (HØY) 00:04:07.150 --> 00:04:18.800 Det fungerte bra, å gå fra x^4 til x^5. Hva med x^6 da? (x^6)', hvordan skulle jeg regne ut den? 00:04:18.800 --> 00:04:25.900 Ja, nå jeg kjenner jeg jo den deriverte til x^5, så jeg kan tenke på x^6 som et produkt av x^5 ganget med x. 00:04:25.900 --> 00:04:32.300 Så skal jeg derivere det produktet. Jeg følger akkurat samme strategi som i stad. Nå kjenner jeg 00:04:32.300 --> 00:04:39.800 den deriverte til x^5, så jeg kan bruke produktregelen. Først deriverer jeg x^5. Da så vi ovenfor at 00:04:39.800 --> 00:04:48.200 jeg fikk 5x^4. Så skal jeg la den x-en stå, den står bare der. Neste gang skal jeg la x^5 stå, så den 00:04:48.200 --> 00:04:53.950 er bare med her. Og så skal jeg derivere x-en, og det gir meg 1. NOTE Treffsikkerhet: 92% (HØY) 00:04:53.950 --> 00:05:04.900 Akkurat det samme skjer her som i stad. Her har jeg en x^5, eller jeg har 5 av dem. Her har jeg en x^5, 00:05:04.900 --> 00:05:15.600 så i alt får jeg 6x^5. Igjen, passer med mønsteret. Deriverer jeg en potens av x, så får jeg potensen ned foran, 00:05:15.600 --> 00:05:24.600 og så får jeg en eksponent lavere enn det jeg hadde i utgangspunktet. Alt dette her bekrefter hypotesen min. 00:05:24.600 --> 00:05:30.300 Det er også et mønster her som gjør at vi vet hvordan vi skal gå frem for å teste hypotesen for x^7 nå. 00:05:30.300 --> 00:05:37.700 Da skriver jeg bare x^7 som (x^6)*x, og så deriverer jeg på samme måten som her. Og så får jeg 00:05:37.700 --> 00:05:44.150 forhåpentligvis fram at den deriverte av x^7 er 7x^6. NOTE Treffsikkerhet: 93% (HØY) 00:05:44.150 --> 00:05:52.700 Vi skal bruke denne metoden for å derivere x i en veldig høy potens, x^10 000 eller noe sånt. Skal vi gå fram 00:05:52.700 --> 00:06:01.200 fra x^6, til x^7, til x^8 osv, så blir det veldig tungt. Spørsmålet er, er det en metode, slik at vi kan bevise 00:06:01.200 --> 00:06:05.400 dette her en gang for alle? Det er der induksjon kommer inn. NOTE Treffsikkerhet: 91% (HØY) 00:06:05.400 --> 00:06:15.100 La oss prøve å se litt mer systematisk på hva vi har gjort. Vi har vel skaffet oss en liten hypotese 00:06:15.100 --> 00:06:23.400 om hvordan det står til med derivasjon. Hvis jeg tar x^n og deriverer, så får jeg nx^(n-1). 00:06:23.400 --> 00:06:33.000 Jeg har også testet dette her for forskjellige verdier av n. 00:06:33.000 --> 00:06:41.100 Jeg kom så langt opp som til 6 på forrige tavle. Det betyr at jeg vet 00:06:41.100 --> 00:06:47.900 at denne påstanden er sann for n=1,2,3 osv oppover. Men jeg vet også noe mer, for jeg 00:06:47.900 --> 00:06:55.000 hadde jo en liten strategi for hvordan jeg skulle gå videre, hvordan jeg kommer fra 4 til 5, og fra 5 til 6. 00:06:55.000 --> 00:07:02.400 Jeg antydet også at slik kunne vi komme fra 6 til 7. Hvordan er den metoden for å komme et skritt videre? NOTE Treffsikkerhet: 92% (HØY) 00:07:02.400 --> 00:07:09.200 Jo, det vi tenkte oss var at hvis jeg nå visste at den formelen var sann for en k-verdi, altså at 00:07:09.200 --> 00:07:15.700 jeg visste at den deriverte av x^k fulgte det mønsteret for en k, så var trikset å finne 00:07:15.700 --> 00:07:24.600 den deriverte til x^(k+1). Det var å splitte den i to biter. x^k som den ene faktoren, og den kjenner jeg jo 00:07:24.600 --> 00:07:31.700 den deriverte til, og en x etterpå. Kunne forsåvidt ha spaltet dette uttrykket som et produkt på 00:07:31.700 --> 00:07:36.600 andre måter også, men for å holde litt systematikk så gjør jeg det på denne måten her hele tiden. Nå skal jeg 00:07:36.600 --> 00:07:43.200 derivere dette produktet her. Da kan jeg bruke produktregelen, samt det jeg vet at regelen vår gjelder 00:07:43.200 --> 00:07:51.800 for x^k. Deriverer jeg den, så får jeg på kx^k-1, og så må jeg huske på å ta med den x-en der. 00:07:51.800 --> 00:07:58.600 Da har jeg derivert første leddet og latt andre stå. Nå skal jeg la første faktor stå, så da får jeg 00:07:58.600 --> 00:08:02.500 x^k, og så skal jeg derivere x-en som er 1. NOTE Treffsikkerhet: 91% (HØY) 00:08:02.500 --> 00:08:09.800 Så skjer akkurat det samme som i stad. Disse to her kan jeg slå sammen til x^k. Da har jeg k av 00:08:09.800 --> 00:08:22.200 disse x-potensene der, en til der borte. Så jeg får (k + 1)x^k. Dermed ser jeg at denne regelen 00:08:22.200 --> 00:08:29.700 gjelder også for k+1, for her har jeg tatt en potens av x og derivert den. Da får jeg eksponenten 00:08:29.700 --> 00:08:38.100 foran som faktor, og så mister jeg et 1-tall oppi eksponenten, så jeg får fra k+1 til k. 00:08:38.100 --> 00:08:45.500 Dette argumentet viser altså at dersom jeg vet at regelen gjelder for x^k, for et tall k jeg 00:08:45.500 --> 00:08:51.950 ikke har spesifisert, så gjelder det også for k+1. Det er dette her som er hele poenget med induksjon. NOTE Treffsikkerhet: 89% (HØY) 00:08:51.950 --> 00:08:58.300 La meg prøve å illustrere hva som foregår ved å tegne tallinjen bortover her. Så kan jeg sette opp tallene, 00:08:58.300 --> 00:09:14.800 1, 2, 3, 4, 5, 6, 7, 8 og 9. Så skal jeg da prøve å markere de tallene hvor jeg vet at denne formelen holder. 00:09:14.800 --> 00:09:25.100 Jeg hadde sjekket innledningsvis, den gjelder for n=1,2,3,4. 00:09:25.100 --> 00:09:32.700 Så langt hadde jeg skrevet opp til å begynne med. Så viste jeg da at den gjelder for 5 og 6. 00:09:32.700 --> 00:09:38.400 Så langt var jeg kommet tidligere. NOTE Treffsikkerhet: 91% (HØY) 00:09:38.400 --> 00:09:46.000 I tillegg har jeg denne generelle formelen, etter utledningen jeg hadde her, som viser at hvis 00:09:46.000 --> 00:09:54.800 noe gjelder for en k-verdi, hvis x^k følger dette mønsteret, så vil k+1 også gjøre det. Da kan jeg 00:09:54.800 --> 00:10:04.600 gå videre. Jeg vet nå at formelen gjelder for k=6. Da sier det regnestykket her oppe at den også gjelder 00:10:04.600 --> 00:10:12.400 for den neste k-verdien, altså for 7. Så siden jeg vet at den gjelder for 6, så viser dette argumentet her, 00:10:12.400 --> 00:10:20.200 ved å bruke k=6, at den gjelder for 7. Nå kan jeg bruke dette argumentet her oppe med k=7. Da går jeg fra 7 00:10:20.200 --> 00:10:26.500 til neste, og det er 8. Da vet jeg at det gjelder for 8. Så kan jeg bruke akkurat den samme formelen, 00:10:26.500 --> 00:10:32.600 nå som jeg vet at den er sann for k=8. Da har jeg den der, da viser regnestykket at den gjelder for 00:10:32.600 --> 00:10:34.900 neste k-verdi, altså for 9. NOTE Treffsikkerhet: 92% (HØY) 00:10:34.900 --> 00:10:42.600 Sånn kan jeg gå hele veien utover. Neste gang får jeg 10, så får jeg 11 osv. Hvis jeg har et helt tall 00:10:42.600 --> 00:10:50.000 her ute, uansett hvor stort det er, så vil denne prosessen før eller senere komme fram 00:10:50.000 --> 00:10:57.400 til det tallet, og vise at formelen vår også er sann for dette tallet langt der ute. Men jeg slipper 00:10:57.400 --> 00:11:03.800 å gjøre alle disse prosessene for hånd, fordi dette regnestykket gjelder for alle k, og viser oss at alle 00:11:03.800 --> 00:11:11.700 disse sprangene vil gjelde. På denne måten, ved å gjøre et regnestykke for en generell k, så greier jeg å vise at 00:11:11.700 --> 00:11:17.600 jeg alltid kan komme fra et tall til det neste. Hvis da ting er ok til å begynne med, det hadde vært nok 00:11:17.600 --> 00:11:24.900 å vise at denne tingen her var sann for n=1, så kunne jeg alltid komme fra et tall til det neste, 00:11:24.900 --> 00:11:33.600 og da får jeg dekket alle de naturlige tallene. Dette er ideen bak induksjonsbevis. Vi vet at en påstand 00:11:33.600 --> 00:11:34.950 er sann til å begynne med, NOTE Treffsikkerhet: 86% (HØY) 00:11:34.950 --> 00:11:41.600 her for n=1, og så viser vi at det nødvendigvis er sånn at hvis påstanden holder for et naturlig tall, 00:11:41.600 --> 00:11:51.200 så holder den for det neste. Da vil denne hoppeprosessen her overbevise oss om at påstanden er sann for alle n. 00:11:51.200 --> 00:11:56.900 Dette var et eksempel med den deriverte av x^n. Jeg skal nå skrive opp litt mer generelt hvordan vi kan 00:11:56.900 --> 00:11:58.400 formulere induksjonsprinsippet. NOTE Treffsikkerhet: 89% (HØY) 00:11:58.400 --> 00:12:05.700 La oss nå skrive opp dette prinsippet generelt som vi har sett i et spesielt eksempel så langt. 00:12:05.700 --> 00:12:23.800 Vi kaller det prinsippet om induksjon, eller induksjonsprinsippet. Det vi hadde istad, var jo en påstand 00:12:23.800 --> 00:12:30.400 for hvert naturlige tall n, nemlig at den deriverte av x^n hadde en spesiell form. I det generelle prinsippet 00:12:30.400 --> 00:12:41.400 så har vi da bare en påstand. "Anta at vi har en påstand." Det er bare et utsagn som enten er sant eller galt. 00:12:41.400 --> 00:12:58.600 "en påstand P(n) om hvert naturlige tall n, altså n=1,2,3..." NOTE Treffsikkerhet: 86% (HØY) 00:12:58.600 --> 00:13:02.700 og så videre oppover. NOTE Treffsikkerhet: 92% (HØY) 00:13:03.200 --> 00:13:15.800 "... slik at" vi vet følgende to ting. For det første, at det første utsagnet blir P1, siden vi begynner 00:13:15.800 --> 00:13:34.400 å telle på 1. "P(1) er sann". Så det andre utsagnet, som var måten jeg kommer fra et tall til det neste på. 00:13:34.400 --> 00:13:55.900 "Hver gang P(k) er sann, så er P(k+1) også sann". Med det mener jeg å si at hver gang vi har et tall k 00:13:55.900 --> 00:14:03.800 slik at P(k) er sann, så er også det påfølgende utsagnet P(k+1) sant. Da sier dette prinsippet; NOTE Treffsikkerhet: 92% (HØY) 00:14:03.800 --> 00:14:20.800 "Da er P(n) sann for alle n=1,2,3,..." osv oppover. Det er det generelle prinsippet 00:14:20.800 --> 00:14:30.300 om induksjon. Vi har en påstand for hvert av de naturlig tallene, og så vet vi da to ting om 00:14:30.300 --> 00:14:36.100 disse påstandene, nemlig at den første påstanden er sann. Hver gang vi har etablert at en påstand er sann, 00:14:36.100 --> 00:14:43.400 så er nødvendigvis den neste sann. Ut ifra de to forutsetningene, kan vi trekke konklusjonen at P(n) er sann 00:14:43.400 --> 00:14:51.600 for alle naturlige tall. Ideen, grunnen til at dette holder, er akkurat den samme figuren som 00:14:51.600 --> 00:15:03.600 jeg hadde i stad. Hvis jeg tegner heltallene utover her; 1, 2, 3, 4, 5 osv. og jeg markerer de tallene der 00:15:03.600 --> 00:15:03.950 NOTE Treffsikkerhet: 92% (HØY) 00:15:03.950 --> 00:15:11.300 påstanden er sann, så vet jeg jo at P(1) er sann, for det ligger i den første premissen her. Så vet jeg jo at 00:15:11.300 --> 00:15:19.300 siden P(1) er sann, så må P(2) nødvendigvis være det. Det er slik at hver gang påstanden er sann for et tall, 00:15:19.300 --> 00:15:24.900 så er den også sann for det påfølgende tallet. Hvis P(1) er sann, så må P(2) nødvendigvis være det. 00:15:24.900 --> 00:15:34.800 Men når jeg nå vet at P(2) er sann, så må P(3) være sann, og når jeg vet at P(3) er sann, så må P(4) være sann. 00:15:34.800 --> 00:15:40.900 Jeg kan fortsette på den måten. Vi var jo enige om at jeg kom til et hvilken som helst 00:15:40.900 --> 00:15:47.400 naturlig tall, hvis jeg bare holdt på lenge nok å gå fra 1, så har jeg et naturlig tall her nede. 00:15:47.400 --> 00:15:55.000 Så vil denne prosessen, før eller senere, nå opp til det tallet og etablere at P for det tallet er sann. 00:15:55.000 --> 00:16:00.500 Siden dette er et hvilket som helst tall, så betyr det at P(n) må være sann for alle P. NOTE Treffsikkerhet: 88% (HØY) 00:16:00.500 --> 00:16:08.400 Så dette er det abstrakte induksjonsprinsippet. Det sier at hvis vi ønsker å bevise noe for et hvilket 00:16:08.400 --> 00:16:14.200 som helst tall n, altså en påstand P(1) for en hvilken som helst n, ja så kan det ofte være lurt å 00:16:14.200 --> 00:16:19.900 første etablere at P(1) er sann, bare sjekke det. Så ved et abstrakt resonnement vise at dersom 00:16:19.900 --> 00:16:26.400 påstanden er sann for en k, så er den sann for den neste k. Da forteller induksjonsprinsippet oss 00:16:26.400 --> 00:16:31.450 og dette argumentet som ligger bak, at påstanden er sann for alle n. NOTE Treffsikkerhet: 91% (HØY) 00:16:31.450 --> 00:16:38.900 Det er det abstrakte prinsippet. Nå skal vi se på hvordan det kan brukes på to eksempler til. NOTE Treffsikkerhet: 91% (HØY) 00:16:38.900 --> 00:16:48.100 La oss se på et eksempel til hvor vi kan bruke induksjon. Det jeg skal se på, er summer av oddetall. 00:16:48.100 --> 00:16:57.200 Det første oddetallet er 1. Det neste oddetallet er 3. Hvis jeg legger sammen de to første oddetallene, 00:16:57.200 --> 00:17:10.000 så får jeg 1+3. Så kan jeg fortsette og ta et oddetall til. 1 + 3 + 5, det neste er 7. 1 + 3 + 5 + 7 osv. Her har jeg tatt summen av 00:17:10.000 --> 00:17:15.599 bare det første oddetallet, her har jeg tatt summen av de to første, her har jeg tatt summen av de tre første, 00:17:15.599 --> 00:17:23.300 og her har jeg tatt summen av de fire første. Hvis vi nå regner ut hva disse summene er, hva får jeg da? 00:17:23.300 --> 00:17:32.800 Her får jeg 1 selvfølgelig. Her får jeg 1+3=4. Her får jeg 1+3=4+5=9 og så får jeg 00:17:32.800 --> 00:17:38.850 de første her summert opp til 9, og så får jeg 7 til, det blir 16. NOTE Treffsikkerhet: 90% (HØY) 00:17:38.850 --> 00:17:47.300 Vi ser at de tallene som fremkommer her, det er faktisk de første kvadrattallene. Dette her er 1^2. 00:17:47.300 --> 00:18:02.300 Dette er 2^2. Dette er 3^2, og dette er 4^2. Så det ser ut som summen av de 00:18:02.300 --> 00:18:11.200 n første kvadrattallene, om det er 1, 2, 3 eller 4, alltid er dette tallet kvadrert. Man kan jo bli litt tvilende 00:18:11.200 --> 00:18:21.100 og lure på om dette fortsetter. Hvis vi tar med det femte, hva får vi da? Altså 1+3+5+7+9, hvor mye har 00:18:21.100 --> 00:18:28.700 vi da? Fra i stad vet jeg at jeg hvis jeg summerer de første opp til 7, så har jeg 16. Så legger jeg til 9, 00:18:28.700 --> 00:18:33.550 da får jeg 25, som er 5^2. NOTE Treffsikkerhet: 87% (HØY) 00:18:33.550 --> 00:18:42.900 Vi får en sterkere og sterkere indikasjon på at vi har en sammenheng her. Jeg kan lage 00:18:42.900 --> 00:18:50.750 en hypotese om at summen av de n første oddetallene er n^2. NOTE Treffsikkerhet: 91% (HØY) 00:18:50.750 --> 00:19:15.900 La oss skrive opp denne hypotesen. "Summen av de n første oddetallene er n^2." 00:19:15.900 --> 00:19:22.800 Denne hypotesen har jeg akkurat på den formen som vi hadde i stad, nemlig et utsagn om hver n. 00:19:22.800 --> 00:19:31.200 Kan tenke på P(n) som utsagnet, summen av de n første oddetallene, er n^2. at Så har vi sjekket at 00:19:31.200 --> 00:19:37.300 dette utsagnet holder for de første verdiene av n. Her er det naturlig å prøve å bruke induksjon 00:19:37.300 --> 00:19:41.350 på å bevise denne hypotesen her. NOTE Treffsikkerhet: 91% (HØY) 00:19:41.350 --> 00:19:47.600 Siden vi allerede vet at påstanden gjelder for n=1, så er det da ifølge induksjonsprinsippet 00:19:47.600 --> 00:19:56.300 nok å vise at vi kan gå fra et tall til det neste, altså at hvis P(k) gjelder, så gjelder nødvendigvis P(k+1). 00:19:56.300 --> 00:20:03.700 Så det er strategien for å prøve å bevise at dette her er et generelt utsagn. NOTE Treffsikkerhet: 90% (HØY) 00:20:03.700 --> 00:20:11.300 Den prosedyren vi har sett på hittil, den er ganske illustrerende, for det er sånn det ofte skjer at 00:20:11.300 --> 00:20:17.800 matematikere kommer borti problemer de kan løse ved induksjon, nemlig at de oppdager et mønster som gjelder 00:20:17.800 --> 00:20:23.800 for de første heltallsverdiene. Så eksperimenter de litt, ser at det holder videre, så danner de seg en hypotese 00:20:23.800 --> 00:20:29.600 om at dette må være et generelt mønster. Det våpenet man da som regel bruker for å bevise at dette 00:20:29.600 --> 00:20:37.900 faktisk er riktig, det er induksjon. Den første eksperimenterende fasen her er ofte viktig. Det er ikke alltid den 00:20:37.900 --> 00:20:43.400 synes i matematikkoppgaver, for da har ofte noen gjort det arbeidet for oss, og så har de bare stilt opp 00:20:43.400 --> 00:20:46.950 hypotesen uten at vi får være med på eksperimentet til å begynne med. NOTE Treffsikkerhet: 92% (HØY) 00:20:46.950 --> 00:20:54.700 Her har vi en hypotese, og den må vi prøve å bevise. Nå er kanskje den hypotesen 00:20:54.700 --> 00:21:03.300 foreløpig på litt ikke-matematisk form, eller litt for verbal form. Vi har jo bare skrevet den opp 00:21:03.300 --> 00:21:09.400 med ord. Vi har ikke skrevet den opp med en formel. Før vi går videre, må vi kanskje prøve å matematisere 00:21:09.400 --> 00:21:15.100 den littegranne, slik at vi får den på formelform. Så er det lettere å regne med den. 00:21:15.100 --> 00:21:24.100 Hva sier denne her som en formel? Den handler jo om oddetall. Et typisk oddetall ser ut som 2 ganger 00:21:24.100 --> 00:21:34.300 et tall i, minus 1. Slik ser et oddetall ut. Setter jeg inn i=1, så får jeg 2-1=1. Det er 00:21:34.300 --> 00:21:40.900 det første oddetallet. Setter jeg inn i=2, så får jeg 2*2-1=3, som er det andre oddetallet osv. 00:21:40.900 --> 00:21:47.650 Dette her er oddetall nummer i. Det jeg skal summere opp, NOTE Treffsikkerhet: 89% (HØY) 00:21:47.650 --> 00:21:54.400 det er summen av de n første oddetallene, så det betyr at jeg må summere fra det første oddetallet 00:21:54.400 --> 00:22:02.300 i=1, opp til det n-te oddetallet, som jeg får ved å sette inn n her oppe. Dette er matematisk sett 00:22:02.300 --> 00:22:10.100 summen av de n første oddetallene. Det påstanden sier, er at den summen skal være lik n^2. 00:22:10.100 --> 00:22:19.850 Dette er bare en omformulering av den påstanden der oppe, i en litt mer matematisk form. NOTE Treffsikkerhet: 87% (HØY) 00:22:19.850 --> 00:22:25.200 Kanskje litt vanskeligere å se hva den betyr med en gang, men den er lettere å regne med og vi må 00:22:25.200 --> 00:22:27.800 regne med denne her for å til et bevis. NOTE Treffsikkerhet: 91% (HØY) 00:22:27.900 --> 00:22:35.300 La oss se om vi kan bevise hypotesen vår. Vi har sjekket at den stemmer for P(1). 00:22:35.300 --> 00:22:41.200 Ifølge induksjonsprinsippet er det da nok å vise at vi alltid kan komme fra påstand nummer k 00:22:41.200 --> 00:22:55.100 til påstand nummer k+1. Vi antar at påstand P(k) er sann for en k. Hva betyr det? Jo, det betyr at 00:22:55.100 --> 00:23:01.700 dette uttrykket her borte er sant når jeg setter inn k Istedenfor n. Så jeg antar altså at summen 00:23:01.700 --> 00:23:12.100 fra i=1 til k blir det, av 2i-1, det er lik k^2. NOTE Treffsikkerhet: 85% (HØY) 00:23:12.100 --> 00:23:30.300 Den antar jeg er sann, så må jeg da vise at jeg alltid kan få den neste. "Må vise at P(k+1) er sann." NOTE Treffsikkerhet: 91% (HØY) 00:23:30.300 --> 00:23:39.400 Hvordan gjør jeg det? Vel, hva sier P(k+1)? Kanskje vi skal skrive den opp den her borte, så vi vet 00:23:39.400 --> 00:23:50.800 hva vi sikter på. P(k+1) er jo dette utsagnet her med k+1 satt inn for n. Så P(k+1), den vi 00:23:50.800 --> 00:24:05.600 satser på er riktig, den sier da rett og slett at summen fra 1 til k+1 (setter inn k+1 for n), av 2i-1, 00:24:05.600 --> 00:24:13.300 den er (k+1)^2. Det er dette vi skal vise er riktig. Det er greit å skrive det opp, 00:24:13.300 --> 00:24:15.200 for da vet vi hva vi sikter på. NOTE Treffsikkerhet: 91% (HØY) 00:24:15.200 --> 00:24:22.500 Ok, da skriver jeg opp det uttrykket som står på venstresiden der. Det jeg skal vise, 00:24:22.500 --> 00:24:34.900 er at summen i går fra 1 til k+1 av 2i-1. Det er den jeg skal vise nå, 00:24:34.900 --> 00:24:42.000 det er den som inngår i påstanden der borte. Det jeg vet noe om, det er P(k), og det er jo akkurat den samme summen, 00:24:42.000 --> 00:24:49.900 bortsett fra at den går opp til k istedenfor k+1. Hvis jeg deler denne summen i to biter. 00:24:49.900 --> 00:24:55.600 Først tar jeg med de k første leddene, de som inngår i summen her, og så tar jeg det (k+1)-leddet for seg. 00:24:55.600 --> 00:25:07.400 Så får jeg summen i går fra 1 til k, av 2i-1. Der har jeg tatt med de k første leddene. 00:25:07.400 --> 00:25:08.200 NOTE Treffsikkerhet: 90% (HØY) 00:25:08.200 --> 00:25:15.400 Grunnen til at jeg tar med de for seg, er at de vet jeg noe om herfra. Men når jeg har tatt med de k første leddene, 00:25:15.400 --> 00:25:21.500 så har jeg glemt ledd k+1, så det må jeg ta med i tillegg her. Tar med k+1. 00:25:21.500 --> 00:25:30.550 Da skal jeg sette inn i=k+1. Så må jeg huske å trekke fra den -1. NOTE Treffsikkerhet: 89% (HØY) 00:25:30.550 --> 00:25:39.300 Dette ser fryktelig ut. Hvordan skal jeg få til noe her? Vel, jeg får hjelp av induksjonshypotesen, for jeg vet at 00:25:39.300 --> 00:25:47.900 den første summen her er lik k^2. Hele det første uttrykket er lik k^2. Her bruker jeg det 00:25:47.900 --> 00:25:50.300 jeg allerede vet, nemlig at P(k) er sann. NOTE Treffsikkerhet: 88% (HØY) 00:25:50.300 --> 00:25:59.400 Da kan jeg rydde opp litt bak her. 2*k+1, da tar jeg først 2*k. Så får jeg 2*1=2, 00:25:59.400 --> 00:26:06.150 så skal jeg trekke fra 1, så jeg får 2-1=1. NOTE Treffsikkerhet: 91% (HØY) 00:26:06.150 --> 00:26:14.000 Jeg får at den summen her borte, er lik dette uttrykket. Det jeg ønsket å vise, var at den summen var lik (k+1)^2. 00:26:14.000 --> 00:26:20.500 Men her stemmer algebraen ganske godt. Det uttrykket der er jo første kvadratsetning. 00:26:20.500 --> 00:26:30.000 (k+1)^2. Så jeg har faktisk vist akkurat det jeg var 00:26:30.000 --> 00:26:38.400 på jakt etter, nemlig at summen fra 1 til k+1 er (k+1)^2. Akkurat det som var påstanden P(k+1). 00:26:38.400 --> 00:26:39.350 NOTE Treffsikkerhet: 92% (HØY) 00:26:39.350 --> 00:26:47.200 Da har jeg vist at dersom jeg antar at P(k) er sann (den antagelsen brukte jeg når jeg satte den 00:26:47.200 --> 00:26:55.000 stygge summen der lik k^2), dersom jeg antar at P(k) er sann, så viser dette argumentet at P(k+1) er sann. 00:26:55.000 --> 00:27:00.700 Siden det åpenbart gjelder for en hvilken som helst k, så kan jeg da alltid komme et skritt videre. 00:27:00.700 --> 00:27:08.000 Induksjonsprinsippet sikrer hypotesen min, nemlig at denne påstanden er sann for alle naturlige tall n. 00:27:08.000 --> 00:27:18.200 Det siste eksempelet vi skal se på med induksjon handler om en turnering i et spill. Spillet kan ikke 00:27:18.200 --> 00:27:24.000 ende uavgjort. Vi kan tenke på badminton eller biljard. Vi har en turnering 00:27:24.000 --> 00:27:37.000 med n spillere. De spiller alle mot alle, og hver spiller spiller en kamp mot alle de andre. NOTE Treffsikkerhet: 91% (HØY) 00:27:37.000 --> 00:27:45.200 Etter at turneringen er over, så prøver vi å lage en slags uformell rangeringsliste på følgende måte. 00:27:45.200 --> 00:27:52.300 Jeg skal ha en liste over alle spillerne som var med i turneringen. Så skal listen være slik at 00:27:52.300 --> 00:27:58.700 hver spiller har slått den neste på listen. Spiller nr. 1 har slått spiller nr. 2, spiller nr 2 har slått 00:27:58.700 --> 00:28:05.800 spiller nr. 3 og så videre bortover. Det kan selvfølgelig godt tenkes at spiller nr. 4 har slått 00:28:05.800 --> 00:28:11.000 spiller nr. 1 i deres innbyrdes oppgjør, det er ikke noe galt. Det skal bare være slik at hver spiller 00:28:11.000 --> 00:28:18.800 har slått den neste på listen. Spørsmålet er, er det alltid mulig å lage en slik, liste uansett hvor mange 00:28:18.800 --> 00:28:21.150 spillere som er med i turneringen? NOTE Treffsikkerhet: 88% (HØY) 00:28:21.150 --> 00:28:30.100 Dette er jo noe som egner seg for induksjon, i hvert fall i den forstand at vi har en påstand for hver n, 00:28:30.100 --> 00:28:37.100 nemlig at i en turnering med n spillere, så kan vi alltid lage en slik rangeringsliste etterpå, som inneholder 00:28:37.100 --> 00:28:43.400 alle spillerne og der hver spiller på listen har slått nestemann i deres innbyrdes oppgjør. NOTE Treffsikkerhet: 92% (HØY) 00:28:43.700 --> 00:28:50.300 Hvis vi skal bevise noe sånt, må vi kanskje begynne å sjekke nedenfra, med turneringer for 00:28:50.300 --> 00:28:55.600 få spillere. En turnering med en spiller er ikke så veldig mye tess, så vi får kanskje begynne å 00:28:55.600 --> 00:29:01.800 sjekke i en turnering med to spillere. Er det alltid mulig i en slik turnering å rangere spillerne 00:29:01.800 --> 00:29:08.500 etter hverandre? Det er det helt åpenbart her. Er det to spillere, så er det bare spilt et spill, 00:29:08.500 --> 00:29:14.800 nemlig de to imellom. Da har selvfølgelig en vunnet og en tapt i det spillet, siden dette ikke kan ende uavgjort. 00:29:14.800 --> 00:29:21.900 Da setter jeg bare vinneren først og taperen bakerst, så har jeg laget listen. Det viser at 00:29:21.900 --> 00:29:28.900 i turneringer med to spillere, det minst fornuftige tallet, så går dette her greit. Nå så skal jeg prøve 00:29:28.900 --> 00:29:35.300 å bruke induksjon til å komme videre, komme fra k til k+1. Jeg antar at 00:29:35.300 --> 00:29:41.300 jeg allerede vet at i en turnering med to spillere så er dette her alltid mulig. Så skal jeg vise at 00:29:41.300 --> 00:29:44.700 da er det også mulig, i en hvilken som helst turnering, NOTE Treffsikkerhet: 90% (HØY) 00:29:44.700 --> 00:29:53.400 med k+1 spillere. Jeg antar altså at P(k) er sann, nemlig at i enhver turnering med k spillere, 00:29:53.400 --> 00:30:04.800 kan jeg lage en slik liste. Jeg må vise at P(k+1) er sann, nemlig at i enhver turnering med k+1 spillere, 00:30:04.800 --> 00:30:10.700 er det også mulig å lage en slik liste. Hvis vi har vist at vi kan komme fra P(k) til P(k+1), 00:30:10.700 --> 00:30:14.650 så tar induksjonsprinsippet hånd om resten. NOTE Treffsikkerhet: 91% (HØY) 00:30:14.650 --> 00:30:22.200 Hvordan kommer jeg fra P(k) til P(k+1)? Jeg må vise at dersom jeg har en turnering med k+1 spillere, 00:30:22.200 --> 00:30:28.300 så kan jeg lage slik liste. Jeg vet at det kunne jeg gjort, dersom turneringen bare hadde 00:30:28.300 --> 00:30:34.500 hatt k spillere. Da tar vi ganske frekt bort en spiller til å begynne med. 00:30:34.500 --> 00:30:40.400 Jeg plukker en spiller, trekker han ut, sier at vi ser bort ifra dine kamper. Da er det som står igjen, 00:30:40.400 --> 00:30:47.200 å regne som en turnering mellom de k andre spillerne. Etter at jeg har fjernet en spiller, står jeg igjen 00:30:47.200 --> 00:30:54.500 med k. Disse kan jeg rangere etter prinsippet vårt, nemlig at hver spiller har slått den neste 00:30:54.500 --> 00:31:03.300 på lista, rett og slett fordi P(k) er jo antatt å være sann. Her har jeg listen over disse k spillerne, 00:31:03.300 --> 00:31:07.199 hver av dem har slått den neste på lista. NOTE Treffsikkerhet: 92% (HØY) 00:31:07.199 --> 00:31:15.400 Spørsmålet nå er om vi kan få puttet inn den siste spilleren, han vi fjernet, på en fornuftig måte 00:31:15.400 --> 00:31:23.400 uten å ødelegge systemet? Systemet er jo at hver spiller skal ha slått den neste på lista. 00:31:23.400 --> 00:31:29.700 Da er det tre tilfeller vi må se på. To enkle, og en litt mer komplisert. Det aller enkleste som kan skje her, 00:31:29.700 --> 00:31:36.200 er jo at denne spilleren vi har tatt ut, han har faktisk slått førstemann på lista. Hvis han har slått førstemann 00:31:36.200 --> 00:31:41.800 på den lista over de andre spillerne, så kan jeg jo bare putte han på først og så er alt i orden. 00:31:41.800 --> 00:31:50.000 Han har slått nestemann og så vet vi jo at mønsteret holder hele veien ellers. Hvis vår spiller, 00:31:50.000 --> 00:31:55.100 han som vi tok ut av gruppen, faktisk har slått førstemann her, er det lett å lage en liste 00:31:55.100 --> 00:32:01.400 over de P(k+1) spillerne som vi egentlig er interessert i. Tilsvarende, hvis vår spiller, 00:32:01.400 --> 00:32:07.449 han vi tok ut, har tapt for sistemann på lista, så kan jeg føre ham på bakerst her. NOTE Treffsikkerhet: 75% (MEDIUM) 00:32:07.449 --> 00:32:09.700 Så er alt i orden. NOTE Treffsikkerhet: 84% (HØY) 00:32:09.800 --> 00:32:17.650 Problemet, det vanskelige tilfellet, er når vår spiller NOTE Treffsikkerhet: 91% (HØY) 00:32:17.650 --> 00:32:25.200 ikke har vunnet over han her borte, og heller ikke tapt for den spilleren der. Da må vi gå inn 00:32:25.200 --> 00:32:32.000 og se på mønsteret. Hvis vi ser på den spilleren her, så var jo forutsetningen at han her vant over vår spiller. 00:32:32.000 --> 00:32:41.300 Så det er en vinner i duellen med vår spiller. Sistemann her, han hadde jo tapt for vår spiller. 00:32:41.300 --> 00:32:46.400 Hvis han hadde vunnet over vår spiller, kunne vi bare puttet vår spiller bakerst her. Vi vet at han her 00:32:46.400 --> 00:32:53.400 har vunnet over vår spiller, han har tapt for vår spiller. Et eller annet sted inni her må vi skifte fra V-er til T-er. 00:32:53.400 --> 00:33:00.600 Kanskje han har vunnet over vår spiller, han har vunnet over vår spiller, men før eller senere 00:33:00.600 --> 00:33:06.300 må den første T-en dukke opp. Det er en til slutt, så før eller senere må det komme en T. 00:33:06.300 --> 00:33:13.000 Så disse her vunnet over vår spiller, denne har tapt for vår spiller. 00:33:13.000 --> 00:33:18.350 Men da kan vi bare ta vår spiller, han vi tok ut av gruppen i stad, og putte ham inn NOTE Treffsikkerhet: 87% (HØY) 00:33:18.350 --> 00:33:26.100 på listen der sånn. Da er den overgangen der riktig. Den spilleren har vunnet over vår, så det er riktig. 00:33:26.100 --> 00:33:32.200 Den spilleren har tapt for vår, så den overgangen er også riktig. Alle de andre overgangene er riktig, 00:33:32.200 --> 00:33:38.200 for det er jo bygget inn i det opprinnelige systemet når vi bare så på de k spillerne. Ved å putte inn 00:33:38.200 --> 00:33:45.800 vår spiller på det punktet der, når vi går over fra V til T, så har vi laget en liste over de k+1 spillerne 00:33:45.800 --> 00:33:50.800 i den opprinnelige turneringen, som faktisk tilfredsstiller kravene. NOTE Treffsikkerhet: 89% (HØY) 00:33:50.800 --> 00:33:57.800 Det viser altså at dersom P(k) er sann, dersom vi alltid kan lage en liste over k spillere 00:33:57.800 --> 00:34:04.100 som tilfredsstiller kriteriene, så kan vi alltid lage en liste over en turnering med k+1 spillere. 00:34:04.100 --> 00:34:13.000 Dermed har vi gått fra P(k) til P(k+1), og så tar induksjonen seg av resten. Det betyr at i en hvilken som turnering med n spillere, 00:34:13.000 --> 00:34:19.300 uansett hvor stor n er, så kan vi alltid lage en liste av denne typen her.