Vise delelighet ved induksjon

[Genius-Boy]

Har blitt trukket opp i matte R2 eksamen, og gjør øvingsoppgaver til følger og rekker akkurat nå.

Kom over en oppgave som omhandler å vise delelighet ved induksjon. Dette er egentlig ikke så vanskelig, men jeg er uansett litt usikker på det jeg skal sette opp først.

Oppgaven lyder slik:

Vis ved induksjon at

[tex]4^{n}-1[/tex]

er delelig med [tex]3[/tex] for alle hele tall [tex]n\ge0[/tex].

Jeg vet hvordan man skal føre induksjonsbevis; først vise at formelen gjelder for [tex]n=1[/tex], deretter sette (anta at) [tex]n=k[/tex] og til slutt vise at formelen også gjelder for [tex]n=k+1[/tex]. Men hvordan skal jeg sette opp dette beviset (i første trinn altså)?

Jeg vil ikke ha løsning, men kun et svar på hvordan jeg skriver opp stykket.

Selv har jeg skrevet

[tex]0+1+2+3+...+n=\frac{4^{n}-1}{3}[/tex]

Er det riktig?

Takker for alle svar!

[Vektormannen]

Hva har summen [tex]1+2+3+...+n[/tex] med noe å gjøre? Du skal vise at [tex]4^3 - 1[/tex], [tex]4^4-1[/tex], [tex]4^5-1[/tex] osv. er delelige med 3.

Du antar at [tex]4^k - 1[/tex] er delelig med 3. Det kan skrives som at [tex]4^{k+1} - 1 = 3s[/tex] der s er et eller anna tall. Du må så, ved å bruke dette, vise at det også vil gjelde for n = k+1. Bruk at [tex]4^{k+1} - 1 = 4 \cdot 4^k - 1[/tex] og premissen ovenfor til å vise at dette også kan skrives som 3 ganger et tall.

edit: skriveleif

[Genius-Boy]

Aha...tenkte helt feil jeg. Men hvilken funksjon har [tex]s[/tex] i dette uttrykket?

[Vektormannen]

s er bare et eller annet vilkårlig naturlig tall.

Å si at et eller anna tall n = 3s er en måte å si at n er delelig på 3 på. Det sier jo at tallet n er lik et eller annet tilfeldig tall s, men alltid ganger tallet / med faktoren 3.

Dette beviset kan sikkert føres på flere måter, men jeg er hvertfall vant med å innføre slike ligninger som [tex]4^k - 1 = 3s[/tex] for å understreke at noe er delelig på 3. Da kan du bruke 3s senere, i induksjonstrinnet til å vise at det nye tallet også er delelig på 3 (dette kan selvsagt konkluderes uten å bruke at [tex]4^k - 1 = 3s[/tex], men det blir ryddigere da)

edit: et hint til å komme videre her er forresten å trekke fra 3 og legge til 3 (det er jo lov, summen av dem blir jo 0). Da vil du se at du kan gjøre noe smart. Eventuelt kan du bruke at [tex]4^k = 3s + 1[/tex].

[Genius-Boy]

Tror jeg fikk det til nå, ved hjelp av din førstnevnte metode.

Takker for hurtig respons!