Induksjonsbevis

[larsern14]

Bruk induksjon til å bevise at 5^n -1 er delelig med 4

Er litt kjent med induksjonsbevis, men denne oppgaven er annerledes enn andre opppgaver jeg har gjort. Noen som kan hjelpe meg med hvordan jeg går fram?

[Vektormannen]

Å vise for n = 1 er vel greit

Anta at det stemmer for n = k. Dvs. at for et tall k så er [tex]5^k - 1[/tex] delelig med 4. Det kan du uttrykke slik: [tex]5^k - 1 = 4s[/tex], for et eller annet tall s. Din jobb blir nå å se på det neste tallet [tex]5^{k+1} - 1[/tex] og bruke antagelsen om at [tex]5^k -1 = 4s[/tex] til å vise at også det er delelig på 4. (Et litt kryptisk hint: [tex]5 = 4 +1[/tex])

[Nebuchadnezzar]

Et annet hint er at oppgaven er blitt løst før, både i bevisforumet og her =)

EDIT: Slenger opp et alternativt bevis under. Dette er IKKE pensum på videregående, men kan bli lest som en artig tillegsnotis. Når en lærer litt mer matematikk, er dette en lettere måte å bevise setningen på.

La oss anta at vi har to tall, a og b. Og deler a på b. Men divisjonen går ikke opp, vi får en rest. Vi kan si at denne resten er slik at dersom vi trekker resten fra a, går divisjonen opp. Eksempelvis

a = 8 og b = 5

Her ser vi at [tex]\frac{8}{5}[/tex] ikke blir et heltall. Vi legger også merke til at resten blir 3. Siden divisjonen går opp dersom vi skriver
[tex]\frac{8-3}{5}[/tex]
Men vi kunne like gjerne ha valgt -2 siden, da går også divisjonen opp.
[tex]\frac{8-(-2)}{5}[/tex]

Innen matematikken, så har vi en annen mer komptakt skrivemåte for å beskrive sammenhengen mellom delighet og brøker. Nemmlig kongurenser. Dette er bare en annen skrivemåte for å beskrive det ovenfor.

Eksempelvis kan vi skrive

[tex]8 \equiv 3 \pmod{5} \quad \Leftrightarrow \quad = \frac{8-3}{5}=k[/tex]

Der k er et heltall. Angående kongurenser har vi en del regneregler. Vi kan legge til og trekke fra, og også opphøye. Husker du at jeg sa at også -2 passet inn? Dette gjennspeiles i kongurensen ved at

[tex]8 \equiv (3-5) \pmod{5} k[/tex]
[tex]8 \equiv (-2) \pmod{5} k[/tex]

Vi kan legge til og trekke fra faktorer av 5, og ingenting forandrer seg. Nå tilbake til oppgaven din :p Vi vet at

[tex]5 \equiv 1 \pmod{4} [/tex]

Siden dette betyr akkuratt det samme som [tex]\frac{5-1}{4}=k[/tex]

Nå kan vi opphøye begge sider i n, og da får vi

[tex]5^n \equiv 1^n \pmod{4} [/tex]

Mer generellt kan vi også vise at siden

[tex]k \equiv 1 \pmod{k-1} [/tex]

Så

[tex]k^n \equiv 1^n \pmod{k-1} [/tex]
[tex]k^n \equiv 1 \pmod{k-1} [/tex]

Der k er et vilkårlig heltall

[larsern14]

Sliter litt med utregninga. Må jeg brukke logaritme? I så fall hvordan?

[2357]

Neida. Bare kombiner Vektormannens kryptiske hint med at [tex]5^{k+1}-1=5\cdot5^k-1[/tex].

[Nebuchadnezzar]

1. Vi sjekker om det stemmer for n=1

5^1 - 1 er delelig med 4. Greit!

2. Vi antar at det stemmer for en tilfeldig verdi. Altså antar vi at det stemmer for n=k. Altså vi antar at for 5^k - 1 er delelig med 4.

3. Vi skal vise at dersom det stemmer for [tex]n=k[/tex], så stemmer det for det neste tallet. Altså [tex]n=k+1[/tex]

Din jobb er altså å vise at 5^{k+1}-1 er delelig på 4.

Hintet som vektormannen gav, er at [tex]5^{k+1}[/tex] kan skrives som [tex]5\cdot5^{k}[/tex]. Og med en liten snerten omskrivning til er du i mål.

Under er noen fabelaktige videoer om induksjon

http://www.youtube.com/watch?v=OO6vgKaFwGg

[larsern14]

Åjja, nå skjønte jeg det, takk for hjelpen

EDIT: Bra videoserie!

[Hoksalon]

Vet ikke om det er nødvendig, menmen:

[tex]5^n -1 = 4s[/tex]

[tex]5^1 -1 = 4 \ast 1[/tex]

[tex] 5^n -1 = 4s [/tex]

[tex] 5^{n+1} -1 = 4s [/tex]

[tex] (4+1)^{n+1} -1 = 4s[/tex]

[tex] 4^{n+1} + 4^n + 4^{n-1}+...+1 -1 = 4s [/tex]

[tex] 4^n+4^{n-1}+4^{n-2}+...+1 = s[/tex]

[Vektormannen]

Det blir nok ikke helt riktig det der. Når du skriver [tex]5^{n+1} - 1 = 4s[/tex] så antar du at også dette tallet er delelig på 4. Det kan du ikke anta, for det du skal vise er jo at hvis påstanden er sann for n = k så er den sann for n = k+1. Her antar du at den allerede er sann for n = k+1, og du får heller ikke bruk for antagelsen om at n = k er sann.

Det er egentlig ingen grunn til å føre et induksjonsbevis hvis du bruker binomialteoremet. Da kan du bare skrive noe sånt som:

For alle [tex]n > 0[/tex] er
[tex](4+1)^n - 1 = (4^n + 4^{n-1} + ... + 4 + 1) - 1 = 4^n + 4^{n-1} + ... + 4 = 4(4^{n-1} + 4^{n-2} + ... + 1) = 4s[/tex].

Et induksjonsbevis ville vært nødvendig dersom vi ikke klarer å gjøre en slik generell utledning for alle [tex]n[/tex]. Med binomialteoremet og med kongruensregningen som Nebu gjorde ovenfor så kan man det.

[Nebuchadnezzar]

Som vektormannen sier så kan en vel også gjøre en snerten liten omskrivning for det mer generelle tilfelle.

Vi ønsker å vise at [tex]k^n-1[/tex] er delelig på [tex]k-1[/tex] for alle [tex]n[/tex] der [tex]k\in \mathbb{N}[/tex]

Ved hjelp av binomialteoremet, eller at vi faktisk kan bruke polynomdivisjon!
Så kan vi se at

[tex]k^n - 1 = ( k - 1 ) \left( k^{n-1} + k^{n-2} + ... + k^{n-n+1} + k^{n-n}\right) [/tex]

(Ganger vi ut høyreside ser vi at alle leddene untatt første og siste ledd strykes.)

Som åpenbart er delelig på [tex]k -1[/tex].

[viking]

Hvis du ganger ut (4+1)^n må alle leddene utenom ett, nemlig 1^n, inneholde faktoren 4 en eller flere ganger. Dette kan du se uten å kunne matte.

1^n=1, så bare trekk fra dette, og det du har igjen må kunne skrives som 4*(m). Altså delelig med 4.

Det er jo ikke noen grunn til å bruke induksjon her, men hva med å skrive dette er sant for en n (noe det åpenbart er), så blir alle leddene etter du ganger med (4+1) fortsatt delelig med 4 untatt 1*1 som fortsatt er 1.
QED