Forskjellige bevis

[Fibonacci92]

Etter å ha blitt inspirert av den siste oppgaven på eksamen i R1 begynte jeg å lure på hvor mange forskjellige måter vi kan bevise at 4^n -1 er delelig med 3 for alle ikkenegative heltall n.

Alternativt bevise at (k+1)^n -1 er delelig med k for alle ikkenegative heltall n og positive heltall k.

Tenker at dette kan være en grei bevisøving slik at man får sammenliknet forskjellige metoder og sånn.

[Gommle]

Påstand: [tex](k+1)^n -1[/tex] er delelig på [tex]k[/tex] for [tex]n\ge0[/tex] og [tex]k>0[/tex]

n=0:
[tex](k+1)^0 -1 = k[/tex] som opplagt er delelig på [tex]k[/tex].

n=p:
Vi antar at følgende stemmer:
[tex](k+1)^p -1[/tex] er delelig på [tex]k.[/tex]

n=p+1:
[tex](k+1)^{p+1} -1 = (k+1)(k+1)^p - 1 = k(k+1)^p + (k+1)^p - 1[/tex]

[tex]k(k+1)^p[/tex] er opplagt delelig på k, og vi har antatt at [tex](k+1)^p-1[/tex] er delelig på k. Ved induksjon følger det da at (k+1)^n-1 er delelig på k for [tex]n\ge0[/tex] og [tex]k>0[/tex]

[Fibonacci92]

Ser bra ut Gommle.

Kan ta beviset som var på eksamen. (Spesielt for 4^n -1)

4^n - 1 = (2^2)^n - 1 = (2^n)^2 - 1 = (2^n - 1)(2^n + 1)

(2^n -1) , (2^n) , (2^n +1) er tre tall som kommer etter hverandre.

Dermed er et av dem delelig med 3, siden hvert tredje tall er delelig med 3.

2^n består bare av toerfaktorer, og er dermed ikke delelig med 3.

Dermed må enten 2^n -1 eller 2^n +1 være delelig med 3.

Siden 4^n-1= (2^n - 1)(2^n + 1) , og en av faktorene uansett er delelig med 3, så er også 4^n -1 delelig med 3 for alle ikkenegative n.

[Nebuchadnezzar]

Og da kan jo jeg ta induksjonsbeviset, selv om vi har sett det mange ganger før

Påstand: [tex]4^n -1[/tex] er delelig med [tex]3[/tex] når [tex]n\geq 0[/tex]

Vi tester om dette stemmer for n=1

[tex]4^n -1=4-1=3[/tex]

Som åpenbart er delelig med [tex]3[/tex]

vi antar da at [tex]4^k-1[/tex] er delelig på [tex]3[/tex]

Ser om dette stemmer for [tex]k+1[/tex]

[tex]4^{k+1} -1 = 4 \cdot 4^{k} -1 = 4 ( 4^k - 1 ) + 3 [/tex]

Ser vi at begge leddene er delelig med [tex]3[/tex], og dermed følger det av induksjon at [tex]4^n -1[/tex] er delelig på [tex]3[/tex].

[Fibonacci92]

Her er et pent bevis, skal ikke ta æren for det, men husker ikke hvor jeg så det.

Summen av ei geometrisk rekke er jo

k^0 + k^1 + ...... k^(n-1) = (k^n - 1)/(k-1)

Siden summen av rekken blir et heltall går selvfølgelig (k^n - 1) / (k - 1) opp.

Bruker dette for 4^n -1

1 + 4 + 16 + ... + 4^(n-1) = (4^n - 1)/(4-1)

som gir at

4^n - 1 = 3(1 + 4 + 16 .... + 4^(n-1))

og er dermed delelig på 3.

[Karl_Erik]

Noe som neppe er så mye mer enn en vri på beviset som nettopp ble postet er å se på polynomet [tex]p(x)=x^n-1[/tex]. Vi ser at [tex]p(1)=0[/tex], så det finnes et polynom [tex]q(x)[/tex] med heltallige koeffisienter slik at [tex]p(x)=(x-1)q(x)[/tex]. (Er man interessert er [tex]q(x)=x^{n-1}+x^{n-1} + \ldots +1[/tex] , så dette er ikke så mye mer enn geometrisk-rekke-beviset i forkledning.) Vi har da at [tex]4^n-1=p(4)=(4-1) \cdot q(4) = 3 \cdot q(4)[/tex]. [tex]q(4)[/tex] er opplagt et heltall, og vi er ferdige.

Alternativt kan man si at [tex]4^n=(3+1)^n[/tex] og bruke binomialteoremet.

[Fibonacci92]

Hva med moduloregning?:D

4 [symbol:identisk] 1 mod 3

4^n [symbol:identisk] 1^n mod 3

4^n [symbol:identisk] 1 mod 3

4^n -1 [symbol:identisk] 0 mod 3