miniatura|267x267px|Els 89 primers nombres naturals en la forma de Zeckendorf. L'altura de cada rectangle és un nombre de Fibonacci. Les bandes verticals tenen amplada 10. 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 és qualsevol enter positiu, existeixen enters positius , amb , tals que
on és el -èssim nombre de Fibonacci. Aquesta suma s'anomena la representació de Zeckendorf de . La codificació de Fibonacci de es pot derivar de la seva representació de Zeckendorf.
Per example, la representació de Zeckendorf de 64 és
.
Hi ha altres formes de representar 64 com la suma de nombres de Fibonacci
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. 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 té una representació de Zeckendorf. Unicitat: cap enter positiu té dues representacions de Zeckendorf diferents.
La primera part del teorema de Zeckendorf's (existència) es pot demostrar per inducció.
Per a és òbviament certa (ja que són nombres de Fibonacci) Per a obtenim , la suma de dos nombres de Fibonacci no consecutius. Per a n major que 4, si és un nombre de Fibonacci aleshores és trivial. En cas contrari, existeix tal que that . Ara suposem que cada nombre té una representació de Zeckendorf (hipòstesi d'inducció) i considerem . Com que , aleshores té una representació de Zeckendorf. Al mateix temps, i, per tant, la representació de Zeckendorf no conté . Com a conseqüència, es pot representar com la suma de i la representació de Zeckendorf de , 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é com el seu membre més gran compleix que és estrictament menor que el següent nombre de Fibonacci .
El lema es pot demostrar per inducció sobre .
Ara considerem dos conjunts no buits de nombres de Fibonacci no consecutius, i , que tenguin la mateixa suma. Considerem els conjunts and que s'obtenen de i eliminant els elements comuns, és a dir,
Com que i tenien la mateixa suma i s'han eliminat exactament els elements de , els dos conjunts and també han de tenir la mateixa suma.
Ara mostrarem per reducció a l'absurd que almenys un dels conjunts and és buit. Suposem el contrari, és a dir, que i són tots dos no buits i considerem el membre més gran de que sigui i el membre més gran de que sigui . Com que i no contenen elements comuns, . Sense perdre generalitat, suposem que . Aleshores pel lema, la suma de és estrictament menor que i, per tant, també és estrictament menor que , mentre la suma de és com a mínim . Això contradiu el fet que i tenguin la mateixa suma. I es conclou que algun conjunt o ha de ser buit.
Ara suposem (novament sense perdre generalitat) que és buit. Aleshores té suma 0, com també . Però com que només pot contenir enters positius, també ha de ser buit. Es conclou que ∅ la qual cosa implica que . Això demostra que la representació de Zeckendorf és única.
Multiplicació de Fibonacci Es pot definir l'operació següent on , 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.
Representació amb nombres de negafibonacci La seqüència de Fibonacci es pot estendre a índex negtiu 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 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 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 es representa amb una cadena de longitud senar si i només si .
Referències
Enllaços externs
Zeckendorf's theorem at cut-the-knot G.M. Phillips (2001) , "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.
Categoria:Fibonacci Categoria:Teoremes de teoria de nombres Categoria:Teoremes matemàtics