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.
Forskjellige bevis
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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]
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]
http://projecteuler.net/ | fysmat
-
- Abel
- Innlegg: 665
- Registrert: 27/01-2007 22:55
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.
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.
-
- Fibonacci
- Innlegg: 5648
- Registrert: 24/05-2009 14:16
- Sted: NTNU
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].
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].
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
-
- Abel
- Innlegg: 665
- Registrert: 27/01-2007 22:55
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.
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.
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.
Alternativt kan man si at [tex]4^n=(3+1)^n[/tex] og bruke binomialteoremet.
-
- Abel
- Innlegg: 665
- Registrert: 27/01-2007 22:55
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
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