Teorema de Zeckendorf

El teorema de Zeckendorf , que lleva el nombre del matemático aficionado Edouard Zeckendorf , es un resultado sobre la representación de los enteros como sumas de números de Fibonacci . Afirma que todo entero positivo puede representarse de forma única como la suma de uno o más números de Fibonacci distintos , de manera que la suma no incluya dos números de Fibonacci consecutivos. Más precisamente, si N es cualquier entero positivo, existen enteros positivos c _i ≥ 2 , con c _{i + 1} > c _i + 1 , tales que

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

donde F _n es el n- ^ésimo número de Fibonacci. Dicha suma se denomina representación de Zeckendorf de N. La codificación de Fibonacci de N se puede derivar de su representación de Zeckendorf.

Por ejemplo, la representación de Zeckendorf de 64 es

64 = 55 + 8 + 1 .

Existen otras formas de representar el 64 como la suma de los números 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

pero estas no son representaciones de Zeckendorf porque 34 y 21 son números de Fibonacci consecutivos, al igual que 5 y 3.

Para cualquier entero positivo dado, su representación de Zeckendorf se puede encontrar utilizando un algoritmo voraz , eligiendo el mayor número de Fibonacci posible en cada etapa. Por ejemplo, 11 = 8 + 3, mientras que 13 = 13 (no 8 + 5), y 31 = 21 + 8 + 2.

El teorema de Zeckendorf tiene dos partes:

1. Existencia : todo entero positivo n tiene una representación de Zeckendorf.
2. Unicidad : ningún entero positivo n tiene dos representaciones de Zeckendorf diferentes.

La parte de existencia del teorema de Zeckendorf se puede demostrar por inducción . El caso base${\displaystyle n=1}$tiene la representación de Zeckendorf${\displaystyle n=1=F_{2}}$. Suponiendo que todos${\displaystyle k<n}$tener una representación de Zeckendorf dejar${\displaystyle j}$ser tal que${\displaystyle F_{j}<n<F_{j+1}}$. Entonces,${\displaystyle n-F_{j}<n}$Por lo tanto, existe una representación de Zeckendorf para${\displaystyle n-F_{j}}$La suposición${\displaystyle F_{j}<n<F_{j+1}}$también implica que${\displaystyle F_{j-1}=F_{j+1}-F_{j}>n-F_{j}}$Por lo tanto, el mayor número de Fibonacci en la representación de Zeckendorf de${\displaystyle n-F_{j}}$debe ser estrictamente menor que${\displaystyle F_{j-1}}$. Esto implica que la representación de Zenckendorf de${\displaystyle n-F_{j}}$junto con${\displaystyle F_{j}}$es una representación válida de Zeckendorf para${\displaystyle n}$.

Para demostrar la unicidad, se puede utilizar la identidad.

$${\displaystyle \sum _{i=0}^{\lfloor n/2\rfloor -1}F_{n-2i}=F_{n+1}-1}$$

Esto se puede demostrar por inducción o mediante un argumento de conteo en el que uno se da cuenta de que ambos lados de la identidad son dos maneras de contar el número de maneras de escribir.${\displaystyle n}$utilizando sumas de${\displaystyle 1}$y al menos uno${\displaystyle 2}$.

Para llegar a una contradicción, supongamos que hay números enteros.${\displaystyle c_{i}}$, para${\displaystyle i=0,1,\ldots ,r}$, y${\displaystyle d_{i}}$, para${\displaystyle i=0,1,\ldots ,s}$, de tal manera que${\displaystyle c_{0},d_{0}\geq 2}$,${\displaystyle c_{i+1}>c_{i}+1}$,${\displaystyle d_{i+1}>d_{i}+1}$, y

${\displaystyle \sum _{i=0}^{r}F_{c_{i}}=\sum _{i=0}^{s}F_{d_{i}}}$

Las longitudes${\displaystyle r}$y${\displaystyle s}$se puede suponer que es el más pequeño posible.

Si${\displaystyle c_{r}=d_{s}}$, es decir, si los términos más grandes${\displaystyle F_{c_{r}}}$y${\displaystyle F_{d_{s}}}$Si dos representaciones de Zeckendorf son iguales, entonces se pueden eliminar de ambas representaciones y obtener dos nuevas representaciones de Zeckendorf que sean iguales y tengan un menor número de sumandos. Esto contradice que${\displaystyle r,s}$eran los más pequeños posibles. Por lo tanto,${\displaystyle c_{r}\neq d_{s}}$. Cambiando los nombres${\displaystyle c}$y${\displaystyle d}$, si es necesario, se puede suponer que${\displaystyle c_{r}>d_{s}}$. Sin embargo, la suma

${\displaystyle \sum _{i=0}^{s}F_{d_{i}}\leq \sum _{i=0}^{\lfloor d_{s}/2\rfloor -1}F_{d_{s}-2i}=F_{d_{s}+1}-1\leq F_{c_{r}}-1<F_{c_{r}}}$

Aquí la primera desigualdad compara la suma con la de la representación de Zeckendorf, cuyo término más grande es${\displaystyle F_{d_{s}}}$y utiliza los números de Fibonacci más grandes permitidos. Es decir, utiliza cada segundo número de Fibonacci descendente desde${\displaystyle F_{d_{s}}}$y deteniéndose en${\displaystyle F_{2}}$o${\displaystyle F_{3}}$La ecuación es la identidad anterior. Esto demuestra que, incluso si la suma${\displaystyle \sum _{i=0}^{s}F_{d_{s}}}$Utiliza todos los números de Fibonacci más grandes permitidos, su suma sigue siendo estrictamente menor que el término más grande.${\displaystyle F_{c_{r}}}$en la suma${\displaystyle \sum _{i=0}^{r}F_{c_{i}}}$Por lo tanto, no se pueden tener dos representaciones de Zeckendorf diferentes que den la misma suma.

Se puede definir la siguiente operación${\displaystyle a\circ b}$sobre los números naturales a , b : dadas las representaciones de Zeckendorf ${\displaystyle a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)}$y${\displaystyle b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)}$definimos el producto de Fibonacci${\displaystyle a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}.}$

Por ejemplo, la representación de Zeckendorf de 2 es${\displaystyle F_{3}}$y la representación de Zeckendorf de 4 es${\displaystyle F_{4}+F_{2}}$(${\displaystyle F_{1}}$está prohibido en las representaciones), por lo tanto${\displaystyle 2\circ 4=F_{3+4}+F_{3+2}=13+5=18.}$

(El producto no siempre está en forma Zeckendorf. Por ejemplo,${\displaystyle 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}.}$)

Una simple reordenación de sumas muestra que se trata de una operación conmutativa ; sin embargo, Donald Knuth demostró el sorprendente hecho de que esta operación también es asociativa . ^{[ 1 ]}

La secuencia de Fibonacci se puede extender a índices negativos n utilizando la relación de recurrencia reordenada. 

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

que produce la secuencia de números " negafibonacci " que satisfacen

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

Cualquier número entero puede representarse de forma única ^{[ 2 ]} como una suma de números de negafibonacci en la que no se utilizan dos números de negafibonacci consecutivos. Por ejemplo:

• −11 = F ₋₄ + ​​F ₋₆ = (−3) + (−8)
• 12 = F ₋₂ + F ₋₇ = (−1) + 13
• 24 = F ₋₁ + F ₋₄ + ​​F ₋₆ + F ₋₉ = 1 + (−3) + (−8) + 34
• −43 = F ₋₂ + F ₋₇ + F ₋₁₀ = (−1) + 13 + (−55)
• 0 está representado por la suma vacía .

0 = F ₋₁ + F ₋₂ , por ejemplo, por lo que la unicidad de la representación depende de la condición de que no se utilicen dos números de negafibonacci consecutivos.

Esto da como resultado un ^{sistema de codificación de enteros, similar a la representación del teorema de Zeckendorf. En la cadena que representa el entero x, el enésimo} dígito es 1 si F −n aparece en la _suma que representa x ; de lo contrario, ese dígito es 0. Por ejemplo, 24 puede representarse mediante la cadena 100101001, que tiene el dígito 1 en las posiciones 9, 6, 4 y 1, porque 24 = F ₋₁ + F ₋₄ + ​​F ₋₆ + F ₋₉ . El entero x se representa mediante una cadena de longitud impar si y solo si x > 0 .  

• Secuencia completa
• Codificación de Fibonacci
• Fibonacci nim
• numeración de Ostrowski

• Zeckendorf, E. (1972). "Representación de los nombres naturales por une algunos nombres de Fibonacci o de nombres de Lucas". Toro. Soc. R. Ciencias. Lieja (en francés). 41 : 179–182 . ISSN 0037-9565 . Zbl 0252.10011 .  

• Weisstein, Eric W. "Teorema de Zeckendorf" . MundoMatemático .
• Weisstein, Eric W. "Representación de Zeckendorf" . MundoMatemático .
• El teorema de Zeckendorf en el nudo de corte
• GM Phillips (2001) [1994], "Representación de Zeckendorf" , Enciclopedia de Matemáticas , EMS Press
• Secuencia OEIS A101330 (producto de Fibonacci (o círculo) de Knuth)

Este artículo incorpora material de la demostración de que la representación de Zeckendorf de un entero positivo es única en PlanetMath , que está bajo la licencia Creative Commons Attribution/Share-Alike License .