Teorema de Zeckendorf

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 N és qualsevol enter positiu, existeixen enters positius c_i ≥ 2, amb c_i + 1 > c_i + 1, tals que

$N=\sum _{i=0}^{k}F_{c_{i}},$

on F_n é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. Com a tal, el teorema és un exemple de la Llei d'Eponímia de Stigler.

Demostració

El teorema de Zeckendorf té dues parts:

1. Existència: qualsevol enter positiu n té una representació de Zeckendorf.
2. 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 $j$ tal que that F_j < n < F_j + 1 . Ara suposem que cada nombre a < n té una representació de Zeckendorf (hipòstesi d'inducció) i considerem a = n − F_j . Com que a < n, aleshores a té una representació de Zeckendorf. Al mateix temps, a < F_j + 1 − F_j = F_j − 1 , i per tant la representació de Zeckendorf no conté F_j − 1 . Com a conseqüència, n es pot representar com la suma de F_j 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é F_j com el seu membre més gran compleix que és estrictament menor que el següent nombre de Fibonacci F_j + 1 .

El lema es pot demostrar per inducció sobre $j$.

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 $\cap$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 F_s i el membre més gran de T′ que sigui F_t. Com que S′ i T′ no contenen elements comuns, F_s ≠ F_t. Sense perdre generalitat, suposem que F_s < F_t. Aleshores pel lema, la suma de S′ és estrictament menor que F_s + 1 i per tant també és estrictament menor que F_t, mentre la suma de T′ és com a mínim F_t. 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 $a\circ b$ on a, b són nombres naturals de la forma següent: donades les representacions de Zeckendorf$a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)$ and $b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)$ es defineix el producte de Fibonacci

$a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}$

Exemples

La representació de Zeckendorf de 2 és $F_{3}$, i la representació de Zeckendorf de 4 és $F_{4}+F_{2}$ ($F_{1}$ no es té en compte a les representacions). Per tant $2\circ 4=F_{3+4}+F_{3+2}=13+5=18.$

El producte no està sempre en la forma de Zeckendorf. Per exemple:

${\begin{array}{rcl}4\circ 4&=&(F_{4}+F_{2})\circ (F_{4}+F_{2})\\&=&F_{4+4}+2F_{4+2}+F_{2+2}\\&=&21+2\cdot 8+3=40\\&=&F_{9}+F_{5}+F_{2}\end{array}}$

O aquest altre exemple:

${\textstyle {\begin{array}{rl}10\circ 12&=(F_{6}+F_{3})\circ (F_{6}+F_{4}+F_{2})\\=&F_{6+6}+F_{6+4}+F_{6+2}+\\&+F_{3+6}+F_{3+4}+F_{3+2}\\=&F_{12}+F_{10}+F_{8}+F_{9}+F_{7}+F_{5}\\=&144+55+21+34+13+5\\=&272\\=&F_{13}+F_{9}+F_{5}\end{array}}}$

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 n usant la relació de recurrència reordenada:

$F_{n-2}=F_{n}-F_{n-1},$

que dona lloc a la seqüència de nombres de "negafibonacci" que satisfà la relació:

$F_{-n}=(-1)^{n+1}F_{n}.$

Exemples

• $F_{0}=F_{2}-F_{1}=1-1=0$
• $F_{-1}=F_{1}-F_{0}=1-0=1$
• $F_{-2}=F_{0}-F_{-1}=0-1=-1$
• $F_{-3}=F_{-1}-F_{-2}=1-(-1)=2$
• $F_{-4}=F_{-2}-F_{-3}=-1-2=-3$

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:

• ${\begin{array}{rcl}-11&=&F_{-6}+F_{-4}\\&=&(-8)+(-3)\end{array}}$

• ${\begin{array}{rcl}12&=&F_{-7}+F_{-2}\\&=&(+13)+(-1)\end{array}}$
• ${\begin{array}{rcl}24&=&F_{-9}+F_{-6}+F_{-4}+F_{-1}\\&=&(+34)+(-8)+(-3)+(+1)\end{array}}$
• ${\begin{array}{rcl}-43&=&F_{-10}+F_{-7}+F_{-2}\\&=&(-55)+(+13)+(-1)\end{array}}$
• 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 $d_{1},d_{2}\ldots ,d_{n}$ per al número x de la forma següent:

$d_{i}={\begin{cases}1&{\text{si }}F_{-i}{\text{ apareix dins la}}\\&{\text{representació de }}x\\0&{\text{en cas contrari}}\end{cases}}$

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è $24=F_{-9}+F_{-6}+F_{-4}+F_{-1}$.

El nombre enter x es representa amb una cadena de longitud senar si i només si x > 0.

Referències

• 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.