Teorema de Zeckendorf

Sobre la representación única de números enteros como sumas de números de Fibonacci no consecutivos

Los primeros 89 números naturales en forma de Zeckendorf. Cada rectángulo tiene un número de Fibonacci F _j como ancho (número azul en el centro) y F _{j −1} como altura. Las bandas verticales tienen un ancho de 10.

En matemáticas , el teorema de Zeckendorf , llamado así en honor al matemático aficionado belga Edouard Zeckendorf , es un teorema sobre la representación de números enteros como sumas de números de Fibonacci .

El teorema de Zeckendorf establece que todo entero positivo puede representarse de forma única como la suma de uno o más números de Fibonacci distintos, de forma 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. Esta suma se denomina representación Zeckendorf de N. La codificación Fibonacci de N se puede derivar de su representación Zeckendorf.

Por ejemplo, la representación Zeckendorf de 64 es

64 = 55 + 8 + 1 .

Hay otras formas de representar 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 éstas no son representaciones de Zeckendorf porque 34 y 21 son números de Fibonacci consecutivos, al igual que 5 y 3.

Para cualquier número entero positivo dado, su representación Zeckendorf se puede encontrar utilizando un algoritmo voraz , eligiendo el número de Fibonacci más grande posible en cada etapa.

Historia

Si bien el teorema lleva el nombre del autor homónimo que publicó su artículo en 1972, el mismo resultado había sido publicado 20 años antes por Gerrit Lekkerkerker . ^[1] Como tal, el teorema es un ejemplo de la Ley de Eponimia de Stigler .

Prueba

El teorema de Zeckendorf tiene dos partes:

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

La primera parte del teorema de Zeckendorf (existencia) se puede demostrar por inducción . Para n = 1, 2, 3 es claramente cierto (ya que son números de Fibonacci), para n = 4 tenemos 4 = 3 + 1. Si n es un número de Fibonacci, entonces no hay nada que demostrar. De lo contrario, existe j tal que F _j < n < F _{j  + 1.}  Ahora supongamos que cada entero positivo a < n tiene una representación de Zeckendorf (hipótesis de inducción) y consideremos b = n − F _j  . Como b < n , b tiene una representación de Zeckendorf por la hipótesis de inducción. Al mismo tiempo, b = n − F _j < F _{j  + 1} − F _j = F _{j  − 1}  (aplicamos la definición de número de Fibonacci en la última igualdad), por lo que la representación de Zeckendorf de b no contiene a F _{j  − 1}  y, por lo tanto, tampoco contiene a F _j  . Como resultado, n puede representarse como la suma de F _j y la representación Zeckendorf de b , de modo que los números de Fibonacci involucrados en la suma son distintos. ^[2]

La segunda parte del teorema de Zeckendorf (unicidad) requiere el siguiente lema:

Lema : La suma de cualquier conjunto no vacío de números de Fibonacci distintos y no consecutivos cuyo miembro más grande es F _j es estrictamente menor que el siguiente número de Fibonacci más grande F _{j  + 1}  .

El lema se puede demostrar por inducción en j .

Ahora tomemos dos conjuntos no vacíos y de números de Fibonacci distintos y no consecutivos que tengan la misma suma, . Consideremos los conjuntos y que son iguales a y de los cuales se han eliminado los elementos comunes (es decir, y ). Como y tenían la misma suma, y ​​hemos eliminado exactamente los elementos de de ambos conjuntos, y deben tener también la misma suma, . ${\displaystyle S}$ ${\displaystyle T}$ ${\textstyle \sum _{x\in S}x=\sum _{x\in T}x}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S'=S\setminus T}$ ${\displaystyle T'=T\setminus S}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S\cap T}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\textstyle \sum _{x\in S'}x=\sum _{x\in T'}x}$

Ahora demostraremos por contradicción que al menos uno de y es vacío. Supongamos lo contrario, es decir, que y son ambos no vacíos y sea el miembro más grande de F s _y el miembro más grande de F t _. Como y no contienen elementos comunes, F _s ≠ F _t . Sin pérdida de generalidad , supongamos que F _s < F _t . Entonces por el lema, , y, por el hecho de que , , mientras que claramente . Esto contradice el hecho de que y tienen la misma suma, y ​​podemos concluir que o deben ser vacíos. ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\textstyle \sum _{x\in S'}x<F_{s+1}}$ ${\textstyle F_{s}<F_{s+1}\leq F_{t}}$ ${\textstyle \sum _{x\in S'}x<F_{t}}$ ${\textstyle \sum _{x\in T'}x\geq F_{t}}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S'}$ ${\displaystyle T'}$

Supongamos ahora (de nuevo sin pérdida de generalidad) que está vacío. Entonces tiene suma 0, y por lo tanto debe estar vacío . Pero como solo puede contener números enteros positivos, también debe estar vacío. Para concluir: lo que implica , lo que demuestra que cada representación de Zeckendorf es única. ^[2] ${\displaystyle S'}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle T'}$ ${\displaystyle S'=T'=\emptyset }$ ${\displaystyle S=T}$

Multiplicación de Fibonacci

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

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

(El producto no siempre está en formato 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}.}$

Un simple reordenamiento de sumas muestra que esta es una operación conmutativa ; sin embargo, Donald Knuth demostró el hecho sorprendente de que esta operación también es asociativa . ^[3]

Representación con números de negafibonacci

La secuencia de Fibonacci se puede extender hasta el índice negativo  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 ^[4] como una suma de números negafibonacci en la que no se utilizan dos números 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 negafibonacci consecutivos.

Esto da un sistema de codificación de números enteros , similar a la representación del teorema de Zeckendorf. En la cadena que representa el número entero  x , el ^dígito n es 1 si F _−n aparece en la suma que representa x ; ese dígito es 0 en caso contrario. Por ejemplo, 24 puede representarse mediante la cadena 100101001, que tiene el dígito 1 en los lugares 9, 6, 4 y 1, porque 24 = F ₋₁ + F ₋₄ + ​​F ₋₆ + F ₋₉ . El número entero  x se representa mediante una cadena de longitud impar si y solo si x > 0 . 

Véase también

• Secuencia completa
• Codificación de Fibonacci
• El sistema de Fibonacci
• Numeración de Ostrowski

Referencias

1. "Bases de Fibonacci y otras formas de representar números". r-knott.surrey.ac.uk . Consultado el 16 de marzo de 2024 .
2. Henderson, Nik (23 de julio de 2016). "¿Qué es el teorema de Zeckendorf?" (PDF) . Universidad Estatal de Ohio . Consultado el 23 de agosto de 2024 .
3. Knuth, Donald E. (1988). "Multiplicación de Fibonacci" (PDF) . Applied Mathematics Letters . 1 (1): 57–60. doi : 10.1016/0893-9659(88)90176-0 . ISSN  0893-9659. Zbl  0633.10011.
4. Knuth, Donald (11 de diciembre de 2008). Números de Negafibonacci y el plano hiperbólico. Reunión anual de la Asociación Matemática de Estados Unidos. The Fairmont Hotel, San José, CA.

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

Enlaces externos

• Weisstein, Eric W. "Teorema de Zeckendorf". MundoMatemático .
• Weisstein, Eric W. "Representación de Zeckendorf". MundoMatemático .
• Teorema de Zeckendorf al cortar el nudo
• 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 prueba de que la representación Zeckendorf de un entero positivo es única en PlanetMath , que está licenciado bajo la Licencia Creative Commons Atribución/Compartir-Igual .