Zeckendorfs teorem
|
Zeckendorf-representasjon av de 89 første heltallene. Bredden på rektanglene er Fibonacci-tall , mens de tilsvarende høydene har . Rektanglene i samme farge er kongruente.FJeg{\ displaystyle F_ {i}} FJeg-1{\ displaystyle F_ {i-1}}![{\ displaystyle F_ {i-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/568d1e86297003df38984a6f5a10548fbd26b87a)
|
Den teorem Zeckendorf , kalt således fra den matematikeren belgiske Edouard Zeckendorf , er en teorem av additiv tallteori som sørger for at et hvilket som helst naturlig tall kan representeres på en unik måte, som en sum av fibonacci tall separate og ikke sammenhengende. Denne representasjonen kalles Zeckendorf-representasjonen av .
IKKE{\ displaystyle N}
IKKE{\ displaystyle N}![IKKE](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Uttalelse og eksempel
Zeckendorfs teorem - For ethvert naturlig heltall eksisterer det en unik sekvens av heltall , med og slik at
IKKE{\ displaystyle N}
vs.0,...,vs.k{\ displaystyle c_ {0}, \ ldots, c_ {k}}
vs.0≥2{\ displaystyle c_ {0} \ geq 2}
vs.Jeg+1>vs.Jeg+1{\ displaystyle c_ {i + 1}> c_ {i} +1}![{\ displaystyle c_ {i + 1}> c_ {i} +1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23053a008d5111396e3e331b404abe298ae3500d)
IKKE=∑Jeg=0kFvs.Jeg{\ displaystyle N = \ sum _ {i = 0} ^ {k} F_ {c_ {i}}}![{\ displaystyle N = \ sum _ {i = 0} ^ {k} F_ {c_ {i}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/169a342ce976392405e0d2193d922e519149ce56)
,
hvor er det femte Fibonacci-tallet.
Fikke{\ displaystyle F_ {n}}
ikke{\ displaystyle n}![ikke](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
For eksempel representeres av den tomme summen . Zeckendorfs representasjon av tallet er
0{\ displaystyle 0}
100{\ displaystyle 100}![100](https://wikimedia.org/api/rest_v1/media/math/render/svg/0572cd017c6d7936a12737c9d614a2f801f94a36)
100=89+8+3{\ displaystyle 100 = 89 + 8 + 3}![{\ displaystyle 100 = 89 + 8 + 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e9d5ed12089859c4b7cb14616e26663bd86ad1a)
.
Nummeret har andre representasjoner som summen av Fibonacci-tall. Så:
100{\ displaystyle 100}![100](https://wikimedia.org/api/rest_v1/media/math/render/svg/0572cd017c6d7936a12737c9d614a2f801f94a36)
100=89+8+2+1{\ displaystyle 100 = 89 + 8 + 2 + 1}
100=89+5+3+2+1{\ displaystyle 100 = 89 + 5 + 3 + 2 + 1}
100=55+34+8+3{\ displaystyle 100 = 55 + 34 + 8 + 3}
100=55+34+8+2+1{\ displaystyle 100 = 55 + 34 + 8 + 2 + 1}
100=55+34+5+3+2+1{\ displaystyle 100 = 55 + 34 + 5 + 3 + 2 + 1}
100=55+21+1. 3+8+3{\ displaystyle 100 = 55 + 21 + 13 + 8 + 3}
men disse representasjonene inneholder påfølgende Fibonacci-tall. Til en hvilken som helst representasjon av et heltall forbinder vi et binært ord , hvis -te bokstav er hvis vises i representasjonen av og hvis ikke. Dermed er representasjonene ovenfor forbundet med ordene:
IKKE{\ displaystyle N}
ikke{\ displaystyle n}
1{\ displaystyle 1}
Fikke{\ displaystyle F_ {n}}
IKKE{\ displaystyle N}
0{\ displaystyle 0}
100{\ displaystyle 100}![100](https://wikimedia.org/api/rest_v1/media/math/render/svg/0572cd017c6d7936a12737c9d614a2f801f94a36)
1000010100{\ displaystyle 1000010100}
1000010011{\ displaystyle 1000010011}
1000001111{\ displaystyle 1000001111}
110010100{\ displaystyle 110010100}
110010011{\ displaystyle 110010011}
110001111{\ displaystyle 110001111}
101110100{\ displaystyle 101110100}![{\ displaystyle 101110100}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e19bbde9e8e27876fd8e1198203cc84832185e0)
.
Settet med binære ord assosiert med Zeckendorf-representasjoner danner et rasjonelt språk : de er det tomme ordet og ordene som begynner med og ikke inneholder to påfølgende ord . Et vanlig uttrykk for dette språket er
1{\ displaystyle 1}
1{\ displaystyle 1}![1](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
0+1(0+01)∗{\ displaystyle 0 + 1 (0 + 01) ^ {*}}![{\ displaystyle 0 + 1 (0 + 01) ^ {*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0199903e3ff0b9ed69ffef010a71c975b05cd5bc)
.
Den Fibonacci koding av et heltall er, ved definisjon, det binære ord forbundet med sin representasjon, returneres og etterfulgt av et symbol . Så, Fibonacci-kodingen av nummeret er .
1{\ displaystyle 1}
100{\ displaystyle 100}
00101000011{\ displaystyle 00101000011}![{\ displaystyle 00101000011}](https://wikimedia.org/api/rest_v1/media/math/render/svg/383b8de749dd4f743b788c8a44ab0852f4b43a6d)
Historisk notat
Zeckendorf publiserte sitt bevis på teoremet i 1972, da uttalelsen i lang tid var kjent som "Zeckendorfs teorem". Dette paradokset forklares i innledningen til Zeckendorfs artikkel: en annen matematiker, Gerrit Lekkerkerker (en) , skrev beviset på teoremet (og andre resultater) etter en foredrag av Zeckendorf, og 'publisert i 1952, mens han tilskrev Zeckendorf forfatterskap. Ifølge Clark Kimberling var det en artikkel av David E. Daykin, publisert i et prestisjefylt tidsskrift, som bidro til å publisere resultatet og dets forfatter.
Demonstrasjon
Beviset for setningen er i to deler:
1. Eksistens : Eksistensen av representasjonen er bevist ved bruk av den grådige algoritmen eller ved induksjon på .
IKKE{\ displaystyle N}![IKKE](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
To bevis på eksistens
Første bevis
Vi resonnerer ved
induksjon godt begrunnet i det naturlige tallet . Hvis er null, blir den representert av den tomme summen. Ellers enten med , det største Fibonacci-tallet mindre enn eller lik og enten . Ved induksjonshypotese, har en representasjon. Så for et hvilket som helst antall av denne representasjonen, derfor . Representasjonen av , forsterket av , er derfor faktisk en representasjon av .
IKKE{\ displaystyle N}
IKKE{\ displaystyle N}
Fk{\ displaystyle F_ {k}}
k≥2{\ displaystyle k \ geq 2}
IKKE{\ displaystyle N}
M=IKKE-Fk{\ displaystyle M = N-F_ {k}}
M{\ displaystyle M}
Fℓ{\ displaystyle F _ {\ ell}}
Fk+Fℓ≤Fk+M=IKKE<Fk+1=Fk+Fk-1{\ displaystyle F_ {k} + F _ {\ ell} \ leq F_ {k} + M = N <F_ {k + 1} = F_ {k} + F_ {k-1}}
Fℓ<Fk-1{\ displaystyle F _ {\ ell} <F_ {k-1}}
M{\ displaystyle M}
Fk{\ displaystyle F_ {k}}
IKKE{\ displaystyle N}![IKKE](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Andre bevis
Vi resonnerer ved induksjon på heltallet n betraktet. Eksistensen er lett verifisert for små verdier av n . Anta at det er sant for et gitt heltall n, og dekomponere dette heltallet ved å bestille Fibonacci-tallene i stigende rekkefølge. Flere saker skal vurderes:
- Hvis med og , så:
ikke=FJeg1+FJeg2+⋯+FJegs{\ displaystyle n = F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s}}}
4≤Jeg1{\ displaystyle 4 \ leq i_ {1}}
∀j,Jegj+1≥Jegj+2{\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}
ikke+1=F2+FJeg1+FJeg2+⋯+FJegs{\ displaystyle n + 1 = F_ {2} + F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s}}}![{\ displaystyle n + 1 = F_ {2} + F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/338940e024bda1f84d48ac4664200acf803bd3b2)
- Hvis med og (og muligens i så fall vilkårene ikke eksisterer). Så:
ikke=F3+F5+⋯+F2r-1+FJegr+FJegr+1+⋯+FJegs{\ displaystyle n = F_ {3} + F_ {5} + \ cdots + F_ {2r-1} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ { s}}}
Jegr≥2r+2{\ displaystyle i_ {r} \ geq 2r + 2}
∀j,Jegj+1≥Jegj+2{\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}
Jegs=2r-1{\ displaystyle i_ {s} = 2r-1}
FJegr+FJegr+1+⋯+FJegs{\ displaystyle F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}
ikke+1=F2r+FJegr+FJegr+1+⋯+FJegs{\ displaystyle n + 1 = F_ {2r} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}![{\ displaystyle n + 1 = F_ {2r} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a014cfa3cd1361fa8afec6cc21736ccbc07dca89)
- Hvis med og (og muligens i så fall vilkårene ikke eksisterer). Så:
ikke=F2+F4+⋯+F2r-2+FJegr+FJegr+1+⋯+FJegs{\ displaystyle n = F_ {2} + F_ {4} + \ cdots + F_ {2r-2} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ { s}}}
Jegr≥2r+1{\ displaystyle i_ {r} \ geq 2r + 1}
∀j,Jegj+1≥Jegj+2{\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}
Jegs=2r-2{\ displaystyle i_ {s} = 2r-2}
FJegr+FJegr+1+⋯+FJegs{\ displaystyle F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}
ikke+1=F2r-1+FJegr+FJegr+1+⋯+FJegs{\ displaystyle n + 1 = F_ {2r-1} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}![{\ displaystyle n + 1 = F_ {2r-1} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6a3e6911e7b26c52078a108ecfcc4e1e59d41c2)
Dermed innrømmer også en nedbrytning.
ikke+1{\ displaystyle n + 1}
2. Unikt : For denne delen bruker vi følgende lemma:
Lemma - Summen av ethvert ikke-fritt sett med distinkte og ikke-påfølgende Fibonacci-tall, hvis største element er , er strengt mindre enn .
Fj{\ displaystyle F_ {j}}
Fj+1{\ displaystyle F_ {j + 1}}![{\ displaystyle F_ {j + 1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8eb2639af0abb9c43ad2b348608a25981391b39b)
To bevis på lemmaet
Første demonstrasjon
Vi resonnerer ved
enkel induksjon på antall elementer i et slikt sett . Initialisering er øyeblikkelig. For arv, hvis har mer enn ett element, la oss fjerne . Ved induksjonshypotese er summen av de gjenværende elementene strengt mindre enn , derfor er den totale summen strengt mindre enn .
S{\ displaystyle S}
S{\ displaystyle S}
Fj{\ displaystyle F_ {j}}
Fj-1{\ displaystyle F_ {j-1}}
Fj-1+Fj=Fj+1{\ displaystyle F_ {j-1} + F_ {j} = F_ {j + 1}}![{\ displaystyle F_ {j-1} + F_ {j} = F_ {j + 1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d4ebd6064cd5b6988e16f406470ebf812000254)
Andre demonstrasjon
Hvis med . Så:
ikke=FJeg1+FJeg2+⋯+FJegs{\ displaystyle n = F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s}}}
∀j,Jegj+1≥Jegj+2{\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}![{\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0da8a00d71df510895cc0f8b81b61d70a3c99388)
- hvis er jevn:
Jegs{\ displaystyle i_ {s}}
FJeg1+FJeg2+⋯+FJegs-1≤FJegs-2+FJegs-4+⋯+F2{\ displaystyle F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s-1}} \ leq F_ {i_ {s} -2} + F_ {i_ {s} - 4} + \ cdots + F_ {2}}
derfor :
FJeg1+FJeg2+⋯+FJegs-1<FJegs-2+FJegs-4+⋯+F2+1=FJegs-1{\ displaystyle F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s-1}} <F_ {i_ {s} -2} + F_ {i_ {s} -4 } + \ cdots + F_ {2} + 1 = F_ {i_ {s} -1}}
- hvis er rart:
Jegs{\ displaystyle i_ {s}}
FJeg1+FJeg2+⋯+FJegs-1≤FJegs-2+FJegs-4+⋯+F3{\ displaystyle F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s-1}} \ leq F_ {i_ {s} -2} + F_ {i_ {s} - 4} + \ cdots + F_ {3}}
derfor :
FJeg1+FJeg2+⋯+FJegs-1<FJegs-2+FJegs-4+⋯+F3+1=FJegs-1{\ displaystyle F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s-1}} <F_ {i_ {s} -2} + F_ {i_ {s} -4 } + \ cdots + F_ {3} + 1 = F_ {i_ {s} -1}}
Så uansett
FJegs≤ikke<FJegs+FJegs-1=FJegs+1{\ displaystyle F_ {i_ {s}} \ leq n <F_ {i_ {s}} + F_ {i_ {s} -1} = F_ {i_ {s} +1}}![{\ displaystyle F_ {i_ {s}} \ leq n <F_ {i_ {s}} + F_ {i_ {s} -1} = F_ {i_ {s} +1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5de18520546a077cf1d1bfad61c7135b871017d7)
Bevis på unikhet
Vi resonnerer ved induksjon godt begrunnet i det naturlige tallet . I følge lemmaet, i en nedbrytning av , er den største indeksen som forekommer (hvis nedbrytningen er ikke-fri, dvs. hvis ) helt bestemt av . Ved induksjonshypotese er nedbrytningen av (derav resten av nedbrytningen av ) også unik.
IKKE{\ displaystyle N}
IKKE{\ displaystyle N}
k{\ displaystyle k}
Fk{\ displaystyle F_ {k}}
IKKE≠0{\ displaystyle N \ neq 0}
Fk≤IKKE<Fk+1{\ displaystyle F_ {k} \ leq N <F_ {k + 1}}
IKKE-Fk{\ displaystyle N-F_ {k}}
IKKE{\ displaystyle N}![IKKE](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Representasjon av hovedtall
I tabellen betegner representasjonen av som et binært ord.
R(IKKE){\ displaystyle R (N)}
IKKE{\ displaystyle N}![IKKE](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
IKKE{\ displaystyle N}
|
R(IKKE){\ displaystyle R (N)}
|
---|
0
|
0
|
1
|
1
|
2
|
10
|
3
|
100
|
4
|
101
|
5
|
1000
|
6
|
1001
|
7
|
1010
|
8
|
10.000
|
9
|
10001
|
10
|
10010
|
11
|
10100
|
Alternativet 0 og 1 i hver av kolonnene tilsvarer fraværet eller tilstedeværelsen av et rektangel i figuren øverst på siden. Følgende siste sifre er
010010100100⋯{\ displaystyle 010010100100 \ cdots}
Dette er starten på Fibonacci-ordet . Faktisk er det niende symbolet på Fibonacci-ordet 0 eller 1, avhengig av om n er “jevn Fibonacci” eller “odd Fibonacci”.
Variasjoner
Representasjon av Fibonacci antall negative indekser
Sekvensen av Fibonacci-tall kan utvides til negative indekser, siden forholdet
Fikke=Fikke-1+Fikke-2{\ displaystyle F_ {n} = F_ {n-1} + F_ {n-2}}![{\ displaystyle F_ {n} = F_ {n-1} + F_ {n-2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fa6d281e7a54e08aeffeef7458ddc0884333686)
gjør det mulig å beregne fra og fra . Vi har (se tilsvarende del av artikkelen om Fibonacci-tall ):
Fikke-2{\ displaystyle F_ {n-2}}
Fikke{\ displaystyle F_ {n}}
Fikke-1{\ displaystyle F_ {n-1}}![F _ {{n-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61373b860d2d2e4842b10ac0b1c3f90362c2c7d0)
F-ikke=(-1)ikke+1Fikke.{\ displaystyle F _ {- n} = (- 1) ^ {n + 1} F_ {n}.}![{\ displaystyle F _ {- n} = (- 1) ^ {n + 1} F_ {n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28100fff6850e5b4934f783e3b5ec3ece74c55b3)
Hele sekvensen er at
Donald Knuth la merke til at ethvert relativt heltall er summen av Fibonacci-tall av strengt negative indekser som han kaller "Negafibonacci", og representasjonen er unik hvis to benyttede tall ikke er fortløpende. For eksempel :
...,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,...{\ displaystyle \ ldots, -8.5, -3.2, -1,1,0,1,1,2,3,5,8, \ ldots}
-
-11=F-4+F-6=(-3)+(-8){\ displaystyle -11 = F _ {- 4} + F _ {- 6} = (- 3) + (- 8)}
;
-
12=F-2+F-7=(-1)+1. 3{\ displaystyle 12 = F _ {- 2} + F _ {- 7} = (- 1) +13}
;
-
24=F-1+F-4+F-6+F-9=1+(-3)+(-8)+34{\ displaystyle 24 = F _ {- 1} + F _ {- 4} + F _ {- 6} + F _ {- 9} = 1 + (- 3) + (- 8) +34}
;
-
-43=F-2+F-7+F-10=(-1)+1. 3+(-55){\ displaystyle -43 = F _ {- 2} + F _ {- 7} + F _ {- 10} = (- 1) +13 + (- 55)}
.
Som ovenfor forbinder vi med representasjonen av et heltall et binært ord , hvis ith-bokstav er hvis vises i representasjonen av og hvis ikke. Så, er representert av ordet . Vi observerer at heltallet er positivt hvis og bare hvis lengden på det tilknyttede ordet er merkelig.
IKKE{\ displaystyle N}
ikke{\ displaystyle n}
1{\ displaystyle 1}
Fikke{\ displaystyle F_ {n}}
IKKE{\ displaystyle N}
0{\ displaystyle 0}
24{\ displaystyle 24}
100101001{\ displaystyle 100101001}
IKKE{\ displaystyle N}![IKKE](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Fibonacci-multiplikasjon
Donald Knuth ser en operasjon av multiplikasjonen av naturlige tall , og er definert som følger: gitt representasjoner
og det Fibonacci produkt er det hele tall .
på∘b{\ displaystyle a \ circ b}
på{\ displaystyle a}
b{\ displaystyle b}
på=∑Jeg=0kFvs.Jeg(vs.Jeg≥2){\ displaystyle a = \ sum _ {i = 0} ^ {k} F_ {c_ {i}} \; (c_ {i} \ geq 2)}
b=∑j=0lFdj(dj≥2){\ displaystyle b = \ sum _ {j = 0} ^ {l} F_ {d_ {j}} \; (d_ {j} \ geq 2)}
på∘b=∑Jeg=0k∑j=0lFvs.Jeg+dj{\ displaystyle a \ circ b = \ sum _ {i = 0} ^ {k} \ sum _ {j = 0} ^ {l} F_ {c_ {i} + d_ {j}}}![{\ displaystyle a \ circ b = \ sum _ {i = 0} ^ {k} \ sum _ {j = 0} ^ {l} F_ {c_ {i} + d_ {j}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c630cb5b721efccfa8397150e472e42c7298c190)
For eksempel, som og , vi har .
2=F3{\ displaystyle 2 = F_ {3}}
4=F4+F2{\ displaystyle 4 = F_ {4} + F_ {2}}
2∘4=F3+4+F3+2=1. 3+5=18{\ displaystyle 2 \ circ 4 = F_ {3 + 4} + F_ {3 + 2} = 13 + 5 = 18}![{\ displaystyle 2 \ circ 4 = F_ {3 + 4} + F_ {3 + 2} = 13 + 5 = 18}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9551e55556bb9be626adb67a864cb25bd678c6e)
Knuth har bevist det overraskende faktum at denne operasjonen er assosiativ .
Andre suiter
Zeckendorf beviser eksistensen og unikheten, betinget av Lucas- tallrepresentasjonen .
Knuth nevner at Zeckendorfs teorem forblir sant for k-bonacci-sekvenser , forutsatt at vi ikke bruker k påfølgende tall av en slik sekvens.
Aviezri Fraenkel ga en generell uttalelse som utvider de tidligere setningene: La være en serie med heltall. Helt naturlig har nøyaktig en representasjon av formen
1=u0<u1<u2<⋯{\ displaystyle 1 = u_ {0} <u_ {1} <u_ {2} <\ cdots}
IKKE{\ displaystyle N}![IKKE](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
IKKE=dkuk+dk-1uk-1+⋯+d1u1+d0u0{\ displaystyle N = d_ {k} u_ {k} + d_ {k-1} u_ {k-1} + \ cdots + d_ {1} u_ {1} + d_ {0} u_ {0}}![{\ displaystyle N = d_ {k} u_ {k} + d_ {k-1} u_ {k-1} + \ cdots + d_ {1} u_ {1} + d_ {0} u_ {0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fce0fe756c850b09026d23e47bda50e7fce7876)
,
hvor er naturlige tall, forutsatt at
dk,...,d0{\ displaystyle d_ {k}, \ ldots, d_ {0}}![{\ displaystyle d_ {k}, \ ldots, d_ {0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2375870c874e19e13e2e5085a949662a63d1da8)
dJeguJeg+dJeg-1uJeg-1+⋯+d0u0<uJeg+1{\ displaystyle d_ {i} u_ {i} + d_ {i-1} u_ {i-1} + \ cdots + d_ {0} u_ {0} <u_ {i + 1}}![{\ displaystyle d_ {i} u_ {i} + d_ {i-1} u_ {i-1} + \ cdots + d_ {0} u_ {0} <u_ {i + 1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b5c9f2cd15c98fd799f58596c028793de6373de)
for .
Jeg≥0{\ displaystyle i \ geq 0}![i \ geq 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/405e1424cb9c4fc171c433a8e8f04b3e5938e366)
Ostrowski-systemet
Ethvert irrasjonelt tall innrømmer en fortsatt utvidelse av brøkdeler . Hvis vi setter , , , og , det var . Følgende danner grunnlag for et nummereringssystem :
α{\ displaystyle \ alpha}
α=[på0,på1,på2,...]{\ displaystyle \ alpha = [a_ {0}, a_ {1}, a_ {2}, \ ldots]}
s-2=0{\ displaystyle p _ {- 2} = 0}
s-1=1{\ displaystyle p _ {- 1} = 1}
q-2=1{\ displaystyle q _ {- 2} = 1}
q-1=0{\ displaystyle q _ {- 1} = 0}
sikke=påikkesikke-1+sikke-2{\ displaystyle p_ {n} = a_ {n} p_ {n-1} + p_ {n-2}}
qikke=påikkeqikke-1+qikke-2{\ displaystyle q_ {n} = a_ {n} q_ {n-1} + q_ {n-2}}
sikke/qikke=[på0,...,påikke]{\ displaystyle p_ {n} / q_ {n} = [a_ {0}, \ ldots, a_ {n}]}
(qikke){\ displaystyle (q_ {n})}![{\ displaystyle (q_ {n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54879f48839adba8e201d105f693cbcfedf5f0dc)
Ostrowskis teorem - La være et irrasjonelt tall, og være sekvensen til nevnere for konvergensene til den fortsatte brøkdelen av . Ethvert positivt heltall er unikt skrevet som
α{\ displaystyle \ alpha}
(qikke){\ displaystyle (q_ {n})}
α{\ displaystyle \ alpha}
IKKE{\ displaystyle N}![IKKE](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
IKKE=bkqk+⋯+b0q0{\ displaystyle N = b_ {k} q_ {k} + \ cdots + b_ {0} q_ {0}}![{\ displaystyle N = b_ {k} q_ {k} + \ cdots + b_ {0} q_ {0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ad6de9839d6609fae2f2dc518c3216b41f06d9f)
der de er heltall som tilfredsstiller følgende tre betingelser:
bJeg{\ displaystyle b_ {i}}![bi}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40a8c2db2990a53c683e75961826167c5adac7c3)
-
0≤b0<på1{\ displaystyle 0 \ leq b_ {0} <a_ {1}}
;
-
0≤bJeg≤påJeg+1{\ displaystyle 0 \ leq b_ {i} \ leq a_ {i + 1}}
for ;Jeg>0{\ displaystyle i> 0}![i> 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f49f2878fd68a89c3da37eb537198e887cf0293)
- For , hvis , da .Jeg>0{\ displaystyle i> 0}
bJeg=påJeg+1{\ displaystyle b_ {i} = a_ {i + 1}}
bJeg-1=0{\ displaystyle b_ {i-1} = 0}![{\ displaystyle b_ {i-1} = 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/530a1cbee1a2d831c41d4198d2d0b42df2525081)
For golden ratio , det er alle en, det er Fibonacci tallene og de tre forholdene at vilkårene i sum er tydelig og ikke sammenhengende.
påJeg{\ displaystyle a_ {i}}
qikke{\ displaystyle q_ {n}}![q_n](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4de60376835c9362d759da9c14e5aad398f9d21)
Merknader og referanser
(fr) Denne artikkelen er helt eller delvis hentet fra den
engelske Wikipedia- artikkelen med tittelen
" Zeckendorfs teorem " ( se listen over forfattere ) .
-
Édouard Zeckendorf, " Representasjon av naturlige tall med en sum av Fibonacci-tall eller Lucas-tall ", Bull. Soc. Roy. Sci. Liège , vol. 41,1972, s. 179–182.
-
(Nl) Cornelis Gerrit Lekkerkerker, " Voorstelling van natuurlijke getallen door een som van getalle van Fibonacci " ["Representation of natural numbers by a sum of Fibonacci numbers"], Simon Stevin , vol. 29,1952, s. 190-195.
-
(in) Clark Kimberling, " Edouard Zeckendorf [1901-1983] " , Fibonacci Quart. , vol. 36, n o 5,
1998, s. 416–418.
-
(in) OF Daykin, " Representation of Natural Numbers have Sums of Generalized Fibonacci Numbers " , J. London Math. Soc. , vol. 35,1960, s. 143 -60.
-
(i) Donald Knuth, "Negafibonacci Tall og hyperbolicus Plane" Paper presentert på det årlige møtet i MAA , The Fairmont Hotel, San Jose, CA. 2008-12-11 [ online presentasjon ] .
-
(i) Donald E. Knuth , " Fibonacci Multiplication " , Applied Mathematics Letters , vol. 1, n o 1,1988, s. 57-60 ( DOI 10.1016 / 0893-9659 (88) 90176-0 )
-
Øvelse 5.4.2-10 i (i) Donald E. Knuth , The Art of Computer Programming , Vol. 3: Sortering og søk ,1998, 2 nd ed. [ detalj av utgaven ].
-
(i) Aviezri S. Fraenkel, " Systems of Numeration " , Amer. Matte. Månedlig , vol. 92, n o to1985, s. 105-114.
-
Denne setningen tilskrives Alexander Ostrowski (1922). Se:
(en) Jean-Paul Allouche og Jeffrey Shallit , Automatic Sequences: Theory, Applications, Generalizations , Cambridge, Cambridge University Press ,2003, 571 s. ( ISBN 0-521-82332-3 , matematiske vurderinger 1997038 , leses online ), Avsnitt 3.9.
Se også
Relaterte artikler
Eksterne linker
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">