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 Plantilla:Mvar és qualsevol enter positiu, existeixen enters positius Plantilla:Math, amb Plantilla:Math, tals que

$N=\sum _{i=0}^k{F}_{c_i},$

on Plantilla:Mvar és el Plantilla:Mvar-èssim nombre de Fibonacci. Aquesta suma s'anomena la representació de Zeckendorf de Plantilla:Mvar. La codificació de Fibonacci de Plantilla:Mvar es pot derivar de la seva representació de Zeckendorf.

Per example, la representació de Zeckendorf de 64 és

Plantilla:Math.

Hi ha altres formes de representar 64 com la suma de nombres de Fibonacci

Plantilla:Math

Plantilla:Math

Plantilla:Math

Plantilla:Math

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 Plantilla:Mvar té una representació de Zeckendorf.
2. Unicitat: cap enter positiu Plantilla:Mvar té dues representacions de Zeckendorf diferents.

La primera part del teorema de Zeckendorf's (existència) es pot demostrar per inducció.

• Per a Plantilla:Math és òbviament certa (ja que són nombres de Fibonacci)
• Per a Plantilla:Math obtenim Plantilla:Math, la suma de dos nombres de Fibonacci no consecutius.
• Per a n major que 4, si Plantilla:Math és un nombre de Fibonacci aleshores és trivial. En cas contrari, existeix $j$ tal que that Plantilla:Math. Ara suposem que cada nombre Plantilla:Math té una representació de Zeckendorf (hipòstesi d'inducció) i considerem Plantilla:Math. Com que Plantilla:Math, aleshores Plantilla:Mvar té una representació de Zeckendorf. Al mateix temps, Plantilla:Math i, per tant, la representació de Zeckendorf no conté Plantilla:Math. Com a conseqüència, Plantilla:Math es pot representar com la suma de Plantilla:Mvar i la representació de Zeckendorf de Plantilla:Mvar, 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é Plantilla:Mvar com el seu membre més gran compleix que és estrictament menor que el següent nombre de Fibonacci Plantilla:Math.

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

Ara considerem dos conjunts no buits de nombres de Fibonacci no consecutius, Plantilla:Math i Plantilla:Math, que tenguin la mateixa suma. Considerem els conjunts Plantilla:Math and Plantilla:Math que s'obtenen de Plantilla:Math i Plantilla:Math eliminant els elements comuns, és a dir,

Com que Plantilla:Math i Plantilla:Math tenien la mateixa suma i s'han eliminat exactament els elements de Plantilla:Math$\cap$Plantilla:Math, els dos conjunts Plantilla:Math and Plantilla:Math també han de tenir la mateixa suma.

Ara mostrarem per reducció a l'absurd que almenys un dels conjunts Plantilla:Math and Plantilla:Math és buit. Suposem el contrari, és a dir, que Plantilla:Math i Plantilla:Math són tots dos no buits i considerem el membre més gran de Plantilla:Math que sigui Plantilla:Mvar i el membre més gran de Plantilla:Math que sigui Plantilla:Mvar. Com que Plantilla:Math i Plantilla:Math no contenen elements comuns, Plantilla:Math. Sense perdre generalitat, suposem que Plantilla:Math. Aleshores pel lema, la suma de Plantilla:Math és estrictament menor que Plantilla:Math i, per tant, també és estrictament menor que Plantilla:Mvar, mentre la suma de Plantilla:Math és com a mínim Plantilla:Mvar. Això contradiu el fet que Plantilla:Math i Plantilla:Math tenguin la mateixa suma. I es conclou que algun conjunt Plantilla:Math o Plantilla:Math ha de ser buit.

Ara suposem (novament sense perdre generalitat) que Plantilla:Math és buit. Aleshores Plantilla:Math té suma 0, com també Plantilla:Math. Però com que Plantilla:Math només pot contenir enters positius, també ha de ser buit. Es conclou que Plantilla:Math ∅ la qual cosa implica que Plantilla:Math. Això demostra que la representació de Zeckendorf és única.

Multiplicació de Fibonacci

Es pot definir l'operació següent $a\circ b$ on Plantilla:Mvar, Plantilla:Mvar són nombres naturals de la forma següent: donades les representacions de Zeckendorf$a=\sum _{i=0}^k{F}_{c_i}(c_i\ge 2)$ and $b=\sum _{j=0}^l{F}_{d_j}(d_j\ge 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}{ccc}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:

$\begin{array}{cc}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 Plantilla:Mvar 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}{ccc}-11& =& F_{-6}+F_{-4}\\ & =& (-8)+(-3)\end{array}$

• $\begin{array}{ccc}12& =& F_{-7}+F_{-2}\\ & =& (+13)+(-1)\end{array}$
• $\begin{array}{ccc}24& =& F_{-9}+F_{-6}+F_{-4}+F_{-1}\\ & =& (+34)+(-8)+(-3)+(+1)\end{array}$
• $\begin{array}{ccc}-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\dots ,d_n$ per al número Plantilla:Mvar de la forma següent:

$d_i=\{\begin{array}{cc}1& \text{si }{F}_{-i}\text{ apareix dins la}\\ & \text{representació de }x\\ 0& \text{en cas contrari}\end{array}$

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 Plantilla:Mvar es representa amb una cadena de longitud senar si i només si Plantilla:Math.

Referències

• Plantilla:Ref-publicació

Enllaços externs

• Plantilla:MathWorld
• 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.