Teorema de Zeckendorf
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9c/Zeckendorf_representations_89px.svg/267px-Zeckendorf_representations_89px.svg.png)
A matemàtiques, el teorema de Zeckendorf's, anomenat pel matemàtic belga amateur Edouard Zeckendorf, és un teorema sobre la representació dels nombres naturals com a sumes de nombres de Fibonacci.
El teorema de Zeckendorf enuncia que tot enter positiu es pot representar de forma única com la suma d'un o diversos nombres de Fibonacci distints de tal forma que la suma no inclou nombres de Fibonacci consecutius. Més precisament, si N és qualsevol enter positiu, existeixen enters positius ci ≥ 2, amb ci + 1 > ci + 1, tals que
on Fn és el n-èssim nombre de Fibonacci. Aquesta suma s'anomena la representació de Zeckendorf de N. La codificació de Fibonacci de N es pot derivar de la seva representació de Zeckendorf.
Per example, la representació de Zeckendorf de 64 és
- 64 = 55 + 8 + 1.
Hi ha altres formes de representar 64 com la suma de nombres de Fibonacci
- 64 = 55 + 5 + 3 + 1
- 64 = 34 + 21 + 8 + 1
- 64 = 34 + 21 + 5 + 3 + 1
- 64 = 34 + 13 + 8 + 5 + 3 + 1
però aquestes no són representacions de Zeckendorf perquè 34 i 21 són nombres de Fibonacci consecutius, com també ho són 5 i 3.
Per a qualsevol enter positiu, la seva representació de Zeckendorf es pot determinar usant un algorisme voraç, elegint el nombre de Fibonacci més gran possible a cada pas.
Història
Mentre el teorema rep el nom de l'autor epònim que va publicar el seu article al 1972, el mateix resultat havia estat publicat 20 anys enrere per Gerrit Lekkerkerker.[1] Com a tal, el teorema és un exemple de la Llei d'Eponímia de Stigler.
Demostració
El teorema de Zeckendorf té dues parts:
- Existència: qualsevol enter positiu n té una representació de Zeckendorf.
- Unicitat: cap enter positiu n té dues representacions de Zeckendorf diferents.
La primera part del teorema de Zeckendorf's (existència) es pot demostrar per inducció.
- Per a n = 1, 2, 3 és òbviament certa (ja que són nombres de Fibonacci)
- Per a n = 4 obtenim 4 = 3 + 1, la suma de dos nombres de Fibonacci no consecutius.
- Per a n major que 4, si n és un nombre de Fibonacci aleshores és trivial. En cas contrari, existeix tal que that Fj < n < Fj + 1 . Ara suposem que cada nombre a < n té una representació de Zeckendorf (hipòstesi d'inducció) i considerem a = n − Fj . Com que a < n, aleshores a té una representació de Zeckendorf. Al mateix temps, a < Fj + 1 − Fj = Fj − 1 , i per tant la representació de Zeckendorf no conté Fj − 1 . Com a conseqüència, n es pot representar com la suma de Fj i la representació de Zeckendorf de a, de forma que la representació completa no té dos nombres de Fibonacci consecutius.
La segona part del teorema de Zeckendorf (unicitat) necessita el lema següent:
- Lema: La suma de qualsevol conjunt no buit de nombres de Fibonacci distints i no consecutius i que té Fj com el seu membre més gran compleix que és estrictament menor que el següent nombre de Fibonacci Fj + 1 .
El lema es pot demostrar per inducció sobre .
Ara considerem dos conjunts no buits de nombres de Fibonacci no consecutius, S i T, que tenguin la mateixa suma. Considerem els conjunts S′ and T′ que s'obtenen de S i T eliminant els elements comuns, és a dir,
S′ = S \ T
T′ = T \ S
Com que S i T tenien la mateixa suma i s'han eliminat exactament els elements de S T, els dos conjunts S′ and T′ també han de tenir la mateixa suma.
Ara mostrarem per reducció a l'absurd que almenys un dels conjunts S′ and T′ és buit. Suposem el contrari, és a dir, que S′ i T′ són tots dos no buits i considerem el membre més gran de S′ que sigui Fs i el membre més gran de T′ que sigui Ft. Com que S′ i T′ no contenen elements comuns, Fs ≠ Ft. Sense perdre generalitat, suposem que Fs < Ft. Aleshores pel lema, la suma de S′ és estrictament menor que Fs + 1 i per tant també és estrictament menor que Ft, mentre la suma de T′ és com a mínim Ft. Això contradiu el fet que S′ i T′ tenguin la mateixa suma. I es conclou que algun conjunt S′ o T′ ha de ser buit.
Ara suposem (novament sense perdre generalitat) que S′ és buit. Aleshores S′ té suma 0, com també T′. Però com que T′ només pot contenir enters positius, també ha de ser buit. Es conclou que S′ = T′ = ∅ la qual cosa implica que S = T. Això demostra que la representació de Zeckendorf és única.
Multiplicació de Fibonacci
Es pot definir l'operació següent on a, b són nombres naturals de la forma següent: donades les representacions de Zeckendorf and es defineix el producte de Fibonacci
Exemples
La representació de Zeckendorf de 2 és , i la representació de Zeckendorf de 4 és ( no es té en compte a les representacions). Per tant
El producte no està sempre en la forma de Zeckendorf. Per exemple:
O aquest altre exemple:
Propietats
- Una simple reorganització de sumes demostra que l'operació és commutativa
- L'operació també és associativa. Donald Knuth va demostrar aquest fet.[2]
Representació amb nombres de negafibonacci
La seqüència de Fibonacci es pot estendre a índex negtiu n usant la relació de recurrència reordenada:
que dona lloc a la seqüència de nombres de "negafibonacci" que satisfà la relació:
Exemples
Representació única
Qualsevol enter es pot representar de forma única[3] com la suma de nombres de negafibonacci de tal forma que no s'utilitzen dos nombres negafibonacci consecutius. Per exemple:
- 0 es representa com la suma buida.
Això dona un sistema de codificació dels nombres enters, similar a la representació del teorema de Zeckendorf. Es defineix una cadena de dígits per al número x de la forma següent:
Per exemple, 24 es pot representar amb la cadena 100101001, que té el dígit 1 a les posicions 9, 6, 4, i 1, perquè .
El nombre enter x es representa amb una cadena de longitud senar si i només si x > 0.
Referències
- ↑ Historical note on the name Zeckendorf Representation by R Knott, University of Surrey
- ↑ Knuth, Donald E. «Fibonacci multiplication». Applied Mathematics Letters, 1, 1, 1988, pàg. 57–60. DOI: 10.1016/0893-9659(88)90176-0. ISSN: 0893-9659.
- ↑ Knuth, Donald (2008-12-11). "Negafibonacci Numbers and the Hyperbolic Plane" a Annual meeting, Mathematical Association of America.
- Zeckendorf, E. «Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas» (en francès). Bull. Soc. R. Sci. Liège, 41, 1972, pàg. 179–182. ISSN: 0037-9565.
Enllaços externs
- Weisstein, Eric W., «Zeckendorf's Theorem» a MathWorld (en anglès).
- Zeckendorf's theorem at cut-the-knot
- G.M. Phillips (2001) [1994], "Zeckendorf representation", Encyclopedia of Mathematics, EMS Press
- La sucesión de Fibonacci, el teorema de Zeckendorf y un poemario magistral
Aquest article incorpora material de la demostració que la representació de Zeckendorf d'un enter positiu és única de PlanetMath, que té la Llicència Creative Commons Atribució/Compartir-Igual.