Teorema lui Zeckendorf
|
Reprezentarea Zeckendorf a primelor 89 de numere întregi. Lățimile dreptunghiurilor sunt numere Fibonacci , în timp ce înălțimile corespunzătoare au . Dreptunghiurile de aceeași culoare sunt congruente.Feu{\ displaystyle F_ {i}} Feu-1{\ displaystyle F_ {i-1}}![{\ displaystyle F_ {i-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/568d1e86297003df38984a6f5a10548fbd26b87a)
|
Teorema Zeckendorf , numit astfel de matematician belgian Edouard Zeckendorf , este o teoremă de aditiv teoria numerelor , care asigură faptul că orice număr natural poate fi reprezentat într - un mod unic, ca o sumă de numere Fibonacci separate și nu consecutiv. Această reprezentare se numește reprezentarea Zeckendorf a .
NU{\ displaystyle N}
NU{\ displaystyle N}![NU](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Declarație și exemplu
Teorema lui Zeckendorf - Pentru orice număr întreg natural , există o secvență unică de numere întregi , cu și , astfel încât
NU{\ displaystyle N}
vs.0,...,vs.k{\ displaystyle c_ {0}, \ ldots, c_ {k}}
vs.0≥2{\ displaystyle c_ {0} \ geq 2}
vs.eu+1>vs.eu+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)
NU=∑eu=0kFvs.eu{\ 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)
,
unde este numărul -Fibonacci.
Fnu{\ displaystyle F_ {n}}
nu{\ displaystyle n}![nu](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
De exemplu, este reprezentat de suma goală . Reprezentarea numărului de către Zeckendorf este
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)
.
Numărul are alte reprezentări ca suma numerelor Fibonacci. Asa de :
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+13+8+3{\ displaystyle 100 = 55 + 21 + 13 + 8 + 3}
dar aceste reprezentări conțin numere Fibonacci consecutive. La orice reprezentare a unui număr întreg , asociem un cuvânt binar, a cărui -a litera este dacă apare în reprezentarea și dacă nu. Astfel, la reprezentările de mai sus sunt asociate cuvintele:
NU{\ displaystyle N}
nu{\ displaystyle n}
1{\ displaystyle 1}
Fnu{\ displaystyle F_ {n}}
NU{\ 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)
.
Setul de cuvinte binare asociate cu reprezentările Zeckendorf formează un limbaj rațional : sunt cuvântul gol și cuvintele care încep cu și nu conțin două cuvinte consecutive. O expresie regulată a acestui limbaj este
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)
.
Codificarea Fibonacci de un întreg este, prin definiție, cuvântul binar asociat cu reprezentarea sa, a revenit și urmat de un simbol . Deci, codificarea Fibonacci a numărului este .
1{\ displaystyle 1}
100{\ displaystyle 100}
00101000011{\ displaystyle 00101000011}![{\ displaystyle 00101000011}](https://wikimedia.org/api/rest_v1/media/math/render/svg/383b8de749dd4f743b788c8a44ab0852f4b43a6d)
Notă istorică
Zeckendorf și-a publicat dovada teoremei în 1972, când afirmația a fost cunoscută, ca „teorema lui Zeckendorf”, pentru o lungă perioadă de timp. Acest paradox este explicat în introducerea articolului lui Zeckendorf: un alt matematician, Gerrit Lekkerkerker (ro) , a scris dovada teoremei (și a altor rezultate) în urma unei discuții a lui Zeckendorf și a „publicat în 1952, atribuind autorul lui Zeckendorf. Potrivit lui Clark Kimberling , a fost un articol de David E. Daykin, publicat într-o revistă de prestigiu, care a ajutat la publicitatea rezultatului și a autorului acestuia.
Demonstrație
Dovada teoremei este în două părți:
1. Existența : Existența reprezentării este dovedită prin utilizarea algoritmului lacom sau prin inducție pe .
NU{\ displaystyle N}![NU](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Două dovezi ale existenței
Prima dovadă
Raționăm prin
inducție bine întemeiată pe numărul natural . Dacă este zero, este reprezentat de suma goală. În caz contrar, fie , cu , cel mai mare număr Fibonacci mai mic sau egal cu și fie . Prin ipoteză de inducție, are o reprezentare. Deci, pentru orice număr din această reprezentare, prin urmare . Reprezentarea lui , mărită de , este, prin urmare, într-adevăr o reprezentare a .
NU{\ displaystyle N}
NU{\ displaystyle N}
Fk{\ displaystyle F_ {k}}
k≥2{\ displaystyle k \ geq 2}
NU{\ displaystyle N}
M=NU-Fk{\ displaystyle M = N-F_ {k}}
M{\ displaystyle M}
Fℓ{\ displaystyle F _ {\ ell}}
Fk+Fℓ≤Fk+M=NU<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}}
NU{\ displaystyle N}![NU](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
A doua dovadă
Raționăm prin inducție asupra întregului n considerat. Existența este ușor verificată pentru valori mici de n . Să presupunem că este adevărat pentru un număr întreg dat n și descompunem acest număr întreg prin ordonarea numerelor Fibonacci în ordine crescătoare. Trebuie luate în considerare mai multe cazuri:
- Dacă cu și , atunci:
nu=Feu1+Feu2+⋯+Feus{\ displaystyle n = F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s}}}
4≤eu1{\ displaystyle 4 \ leq i_ {1}}
∀j,euj+1≥euj+2{\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}
nu+1=F2+Feu1+Feu2+⋯+Feus{\ 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)
- Dacă cu și (și eventual caz în care termenii nu există). Asa de :
nu=F3+F5+⋯+F2r-1+Feur+Feur+1+⋯+Feus{\ displaystyle n = F_ {3} + F_ {5} + \ cdots + F_ {2r-1} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ { s}}}
eur≥2r+2{\ displaystyle i_ {r} \ geq 2r + 2}
∀j,euj+1≥euj+2{\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}
eus=2r-1{\ displaystyle i_ {s} = 2r-1}
Feur+Feur+1+⋯+Feus{\ displaystyle F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}
nu+1=F2r+Feur+Feur+1+⋯+Feus{\ 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)
- Dacă cu și (și eventual caz în care termenii nu există). Asa de :
nu=F2+F4+⋯+F2r-2+Feur+Feur+1+⋯+Feus{\ displaystyle n = F_ {2} + F_ {4} + \ cdots + F_ {2r-2} + F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ { s}}}
eur≥2r+1{\ displaystyle i_ {r} \ geq 2r + 1}
∀j,euj+1≥euj+2{\ displaystyle \ forall j, i_ {j + 1} \ geq i_ {j} +2}
eus=2r-2{\ displaystyle i_ {s} = 2r-2}
Feur+Feur+1+⋯+Feus{\ displaystyle F_ {i_ {r}} + F_ {i_ {r + 1}} + \ cdots + F_ {i_ {s}}}
nu+1=F2r-1+Feur+Feur+1+⋯+Feus{\ 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)
Astfel, admite și o descompunere.
nu+1{\ displaystyle n + 1}
2. Unicitate : Pentru această parte, folosim următoarea lemă:
Lemă - Suma oricărui set non-vid de numere distincte și non-consecutive Fibonacci, al cărui cel mai mare element este , este strict mai mică decât .
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)
Două dovezi ale lemei
Prima demonstrație
Raționăm printr-o
simplă inducție asupra numărului de elemente ale unui astfel de set . Inițializarea este imediată. Pentru ereditate, dacă are mai multe elemente, să eliminăm . Prin ipoteza inducției, suma elementelor rămase este strict mai mică decât , prin urmare suma totală este strict mai mică decât .
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)
A doua demonstrație
Dacă cu . Asa de :
nu=Feu1+Feu2+⋯+Feus{\ displaystyle n = F_ {i_ {1}} + F_ {i_ {2}} + \ cdots + F_ {i_ {s}}}
∀j,euj+1≥euj+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)
- dacă este egal:
eus{\ displaystyle i_ {s}}
Feu1+Feu2+⋯+Feus-1≤Feus-2+Feus-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}}
prin urmare:
Feu1+Feu2+⋯+Feus-1<Feus-2+Feus-4+⋯+F2+1=Feus-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}}
- dacă este ciudat:
eus{\ displaystyle i_ {s}}
Feu1+Feu2+⋯+Feus-1≤Feus-2+Feus-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}}
prin urmare:
Feu1+Feu2+⋯+Feus-1<Feus-2+Feus-4+⋯+F3+1=Feus-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}}
Deci, în orice caz,
Feus≤nu<Feus+Feus-1=Feus+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)
Dovadă de unicitate
Raționăm prin inducție bine întemeiată pe numărul natural . Potrivit lemei, într-o descompunere a , cel mai mare indice pentru care apare (dacă descompunerea este neocupată, adică dacă ) este determinat în întregime de . Prin ipoteză de inducție, descompunerea (deci restul descompunerii ) este, de asemenea, unică.
NU{\ displaystyle N}
NU{\ displaystyle N}
k{\ displaystyle k}
Fk{\ displaystyle F_ {k}}
NU≠0{\ displaystyle N \ neq 0}
Fk≤NU<Fk+1{\ displaystyle F_ {k} \ leq N <F_ {k + 1}}
NU-Fk{\ displaystyle N-F_ {k}}
NU{\ displaystyle N}![NU](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Reprezentarea numerelor întregi prime
În tabel, denotă reprezentarea ca un cuvânt binar.
R(NU){\ displaystyle R (N)}
NU{\ displaystyle N}![NU](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
NU{\ displaystyle N}
|
R(NU){\ 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
|
Alternanța 0 și 1 în fiecare dintre coloane corespunde absenței sau prezenței unui dreptunghi în figura din partea de sus a paginii. Secvența ultimelor cifre este
010010100100⋯{\ displaystyle 010010100100 \ cdots}
Acesta este începutul cuvântului Fibonacci . Într-adevăr, al n- lea simbol al cuvântului Fibonacci este 0 sau 1, în funcție de dacă n este „Fibonacci par” sau „Fibonacci impar”.
Variații
Reprezentarea prin numere Fibonacci a indicilor negativi
Secvența numerelor Fibonacci poate fi extinsă la indici negativi, deoarece relația
Fnu=Fnu-1+Fnu-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)
permite calcularea din și din . Avem (a se vedea secțiunea corespunzătoare a articolului despre numerele Fibonacci ):
Fnu-2{\ displaystyle F_ {n-2}}
Fnu{\ displaystyle F_ {n}}
Fnu-1{\ displaystyle F_ {n-1}}![F _ {{n-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61373b860d2d2e4842b10ac0b1c3f90362c2c7d0)
F-nu=(-1)nu+1Fnu.{\ 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)
Secvența completă este că
Donald Knuth a observat că orice număr întreg relativ este suma numerelor Fibonacci de indici strict negativi pe care el îi numește „Negafibonacci”, reprezentarea fiind unică dacă două numere utilizate nu sunt consecutive. De exemplu :
...,-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)+13{\ 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)+13+(-55){\ displaystyle -43 = F _ {- 2} + F _ {- 7} + F _ {- 10} = (- 1) +13 + (- 55)}
.
Ca mai sus, asociem cu reprezentarea unui număr întreg un cuvânt binar, a cărui litera a este dacă apare în reprezentarea și dacă nu. Deci, este reprezentat de cuvânt . Observăm că numărul întreg este pozitiv dacă și numai dacă lungimea cuvântului asociat este impar.
NU{\ displaystyle N}
nu{\ displaystyle n}
1{\ displaystyle 1}
Fnu{\ displaystyle F_ {n}}
NU{\ displaystyle N}
0{\ displaystyle 0}
24{\ displaystyle 24}
100101001{\ displaystyle 100101001}
NU{\ displaystyle N}![NU](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Înmulțirea Fibonacci
Donald Knuth consideră că o operație de multiplicare a numerelor întregi naturale și definite după cum urmează: având în vedere reprezentările
și produsul Fibonacci este un întreg .
la∘b{\ displaystyle a \ circ b}
la{\ displaystyle a}
b{\ displaystyle b}
la=∑eu=0kFvs.eu(vs.eu≥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)}
la∘b=∑eu=0k∑j=0lFvs.eu+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)
De exemplu, ca și , avem .
2=F3{\ displaystyle 2 = F_ {3}}
4=F4+F2{\ displaystyle 4 = F_ {4} + F_ {2}}
2∘4=F3+4+F3+2=13+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 a dovedit faptul surprinzător că această operațiune este asociativă .
Alte apartamente
Zeckendorf demonstrează existența și unicitatea, în mod condiționat, pentru reprezentarea numărului Lucas .
Knuth menționează că teorema lui Zeckendorf rămâne adevărată pentru secvențele k-bonacci , cu condiția să nu folosim k numere consecutive ale unei astfel de secvențe.
Aviezri Fraenkel a dat o declarație generală care extinde teoremele anterioare: Fie o serie de numere întregi. Totul natural are exact o reprezentare a formei
1=tu0<tu1<tu2<⋯{\ displaystyle 1 = u_ {0} <u_ {1} <u_ {2} <\ cdots}
NU{\ displaystyle N}![NU](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
NU=dktuk+dk-1tuk-1+⋯+d1tu1+d0tu0{\ 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)
,
unde sunt numerele naturale, cu condiția ca
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)
deutueu+deu-1tueu-1+⋯+d0tu0<tueu+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)
pentru .
eu≥0{\ displaystyle i \ geq 0}![i \ geq 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/405e1424cb9c4fc171c433a8e8f04b3e5938e366)
Sistemul Ostrowski
Orice număr irațional admite o expansiune continuă a fracției . Dacă ne - am stabilit , , , și , a fost . Următoarele formează o bază pentru un sistem de numerotare :
α{\ displaystyle \ alpha}
α=[la0,la1,la2,...]{\ displaystyle \ alpha = [a_ {0}, a_ {1}, a_ {2}, \ ldots]}
p-2=0{\ displaystyle p _ {- 2} = 0}
p-1=1{\ displaystyle p _ {- 1} = 1}
q-2=1{\ displaystyle q _ {- 2} = 1}
q-1=0{\ displaystyle q _ {- 1} = 0}
pnu=lanupnu-1+pnu-2{\ displaystyle p_ {n} = a_ {n} p_ {n-1} + p_ {n-2}}
qnu=lanuqnu-1+qnu-2{\ displaystyle q_ {n} = a_ {n} q_ {n-1} + q_ {n-2}}
pnu/qnu=[la0,...,lanu]{\ displaystyle p_ {n} / q_ {n} = [a_ {0}, \ ldots, a_ {n}]}
(qnu){\ displaystyle (q_ {n})}![{\ displaystyle (q_ {n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54879f48839adba8e201d105f693cbcfedf5f0dc)
Teorema lui Ostrowski - Să fie un număr irațional și să fie secvența numitorilor convergenților fracției continue a . Orice număr întreg pozitiv este scris în mod unic ca
α{\ displaystyle \ alpha}
(qnu){\ displaystyle (q_ {n})}
α{\ displaystyle \ alpha}
NU{\ displaystyle N}![NU](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
NU=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)
unde sunt numere întregi care îndeplinesc următoarele trei condiții:
beu{\ displaystyle b_ {i}}![bi}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40a8c2db2990a53c683e75961826167c5adac7c3)
-
0≤b0<la1{\ displaystyle 0 \ leq b_ {0} <a_ {1}}
;
-
0≤beu≤laeu+1{\ displaystyle 0 \ leq b_ {i} \ leq a_ {i + 1}}
pentru ;eu>0{\ displaystyle i> 0}![i> 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f49f2878fd68a89c3da37eb537198e887cf0293)
- Căci , dacă , atunci .eu>0{\ displaystyle i> 0}
beu=laeu+1{\ displaystyle b_ {i} = a_ {i + 1}}
beu-1=0{\ displaystyle b_ {i-1} = 0}![{\ displaystyle b_ {i-1} = 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/530a1cbee1a2d831c41d4198d2d0b42df2525081)
Pentru raportul auriu , toate sunt 1, sunt numerele Fibonacci și cele trei condiții înseamnă că termenii sumei sunt distincti și nu consecutive.
laeu{\ displaystyle a_ {i}}
qnu{\ displaystyle q_ {n}}![q_n](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4de60376835c9362d759da9c14e5aad398f9d21)
Note și referințe
(fr) Acest articol este preluat parțial sau în totalitate din articolul Wikipedia din
limba engleză intitulat
„ Teorema lui Zeckendorf ” ( vezi lista autorilor ) .
-
Édouard Zeckendorf, „ Reprezentarea numerelor naturale printr-o sumă a numerelor Fibonacci sau a numerelor Lucas ”, Bull. Soc. Roy. Știință. Liège , voi. 41,1972, p. 179–182.
-
(nl) Cornelis Gerrit Lekkerkerker, " Voorstelling van natuurlijke getallen door een som van getalle van Fibonacci " ["Reprezentarea numerelor naturale printr-o sumă a numerelor Fibonacci"], Simon Stevin , vol. 29,1952, p. 190-195.
-
(în) Clark Kimberling, „ Edouard Zeckendorf [1901-1983] ” , Fibonacci Quart. , vol. 36, nr . 5,
1998, p. 416–418.
-
(în) OF Daykin, „ Reprezentarea numerelor naturale au sume de numere Fibonacci generalizate ” , J. London Math. Soc. , vol. 35,1960, p. 143 -60.
-
(în) Donald Knuth, „Numerele Negafibonacci și planul hiperbolic” Lucrare prezentată la reuniunea anuală a MAA , Hotelul Fairmont, San Jose, CA. 2008-12-11 [ prezentare online ] .
-
(în) Donald E. Knuth , „ Fibonacci Multiplication ” , Letters Mathematics Applied , vol. 1, n o 1,1988, p. 57-60 ( DOI 10.1016 / 0893-9659 (88) 90176-0 )
-
Exercițiul 5.4.2-10 în (în) Donald E. Knuth , The Art of Computer Programming , Vol. 3: Sortare și căutare ,1998, A 2 -a ed. [ detaliul ediției ].
-
(în) Aviezri S. Fraenkel, " Sisteme de numerotare " , Amer. Matematica. Lunar , vol. 92, n o 21985, p. 105-114.
-
Această teoremă este atribuită lui Alexander Ostrowski (1922). A se vedea:
(en) Jean-Paul Allouche și Jeffrey Shallit , Automatic Sequences: Theory, Applications, Generalizations , Cambridge, Cambridge University Press ,2003, 571 p. ( ISBN 0-521-82332-3 , Math Reviews 1997038 , citiți online ), Secțiunea 3.9.
Vezi și tu
Articole similare
linkuri externe
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">