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
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
Hay otras formas de representar 64 como la suma de los números de Fibonacci.
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.
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 .
El teorema de Zeckendorf tiene dos partes:
La primera parte del teorema de Zeckendorf (existencia) puede demostrarse 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:
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, .
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.
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]
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
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
(El producto no siempre está en formato Zeckendorf. Por ejemplo, )
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]
La secuencia de Fibonacci se puede extender hasta el índice negativo n utilizando la relación de recurrencia reordenada
que produce la secuencia de números " negafibonacci " que satisfacen
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:
0 = F −1 + F −2 , 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 a x ; en caso contrario, ese dígito es 0. 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 −1 + F −4 + F −6 + F −9 . El número entero x se representa mediante una cadena de longitud impar si y solo si x > 0 .
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 .