En matemáticas , el teorema de Zeckendorf , que lleva el nombre del matemático 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 cada entero positivo se puede representar de forma única como la suma de uno o más números de Fibonacci distintos de tal manera que la suma no incluya dos números de Fibonacci consecutivos. Más precisamente, si N es un número entero positivo, existen números enteros positivos c i ≥ 2 , con c i + 1 > c i + 1 , tal que
donde F n es el n- ésimo número de Fibonacci. Una suma de este tipo se llama la representación Zeckendorf de N . La codificación de Fibonacci de N puede derivarse de su representación Zeckendorf.
Por ejemplo, la representación de 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 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 usando un algoritmo codicioso , eligiendo el mayor número de Fibonacci posible en cada etapa.
Historia
Si bien el teorema lleva el nombre del autor epó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:
- Existencia : todo entero positivo n tiene una representación de Zeckendorf.
- Unicidad : ningún número entero positivo n tiene dos representaciones de Zeckendorf diferentes.
La primera parte del teorema de Zeckendorf (existencia) puede demostrarse por inducción . Para n = 1, 2, 3 es claramente cierto (ya que estos son números de Fibonacci), para n = 4 tenemos 4 = 3 + 1 . Si n es un número de Fibonacci, hemos terminado. De lo contrario, existe j tal que F j < n < F j + 1 . Ahora suponga que cada a < n tiene una representación de Zeckendorf (hipótesis de inducción) y considere a = n - F j . Dado que a < n , a tiene una representación de Zeckendorf. Al mismo tiempo, a < F j + 1 - F j = F j - 1 , por lo que la representación de Zeckendorf de a no contiene F j - 1 . Como resultado, n se puede representar como la suma de F j y la representación de Zeckendorf de a .
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 Fibonacci más grande F j + 1 .
El lema se puede probar por inducción en j .
Ahora tome dos conjuntos no vacíos de números de Fibonacci distintos no consecutivos S y T que tengan la misma suma. Considere los conjuntos S ′ y T ′ que son iguales a S y T de los que se han eliminado los elementos comunes (es decir, S ′ = S \ T y T ′ = T \ S ). Dado que S y T tenían la misma suma, y hemos eliminado exactamente los elementos de S T de ambos conjuntos, S ′ y T ′ también deben tener la misma suma.
Ahora demostraremos por contradicción que al menos uno de S ′ y T ′ está vacío. Suponga lo contrario, es decir, que S ′ y T ′ no están vacíos y que el miembro más grande de S ′ sea F s y el miembro más grande de T ′ sea F t . Como S ′ y T ′ no contienen elementos comunes, F s ≠ F t . Sin pérdida de generalidad , suponga F s < F t . Entonces, según el lema, la suma de S ′ es estrictamente menor que F s + 1 y, por lo tanto, es estrictamente menor que F t , mientras que la suma de T ′ es claramente al menos F t . Esto contradice el hecho de que S ′ y T ′ tienen la misma suma, y podemos concluir que S ′ o T ′ deben estar vacíos.
Ahora suponga (de nuevo sin pérdida de generalidad) que S ′ está vacío. Entonces S ′ tiene una suma 0, y también T ′ . Pero dado que T ′ solo puede contener números enteros positivos, también debe estar vacío. Para concluir: S ′ = T ′ = ∅ lo que implica S = T , lo que demuestra que cada representación de Zeckendorf es única.
Multiplicación de Fibonacci
Se puede definir la siguiente operación sobre números naturales a , b : dadas las representaciones de Zeckendorf y definimos el producto Fibonacci
Por ejemplo, la representación de Zeckendorf de 2 es , y la representación de Zeckendorf de 4 es ( no está permitido en las representaciones), por lo que
(El producto no siempre está en formato Zeckendorf. Por ejemplo, )
Una simple reordenación de las sumas muestra que se trata de una operación conmutativa ; sin embargo, Donald Knuth demostró el hecho sorprendente de que esta operación también es asociativa . [2]
Representación con números de negafibonacci
La secuencia de Fibonacci se puede extender al índice negativo n usando la relación de recurrencia reordenada
que produce la secuencia de números " negafibonacci " que satisfacen
Cualquier número entero se puede representar de forma única [3] como una suma de números de negafibonacci en los que no se utilizan dos números de negafibonacci consecutivos. Por ejemplo:
- −11 = F −4 + F −6 = (−3) + (−8)
- 12 = F −2 + F −7 = (−1) + 13
- 24 = F −1 + F −4 + F −6 + F −9 = 1 + (−3) + (−8) + 34
- −43 = F −2 + F −7 + F −10 = (−1) + 13 + (−55)
- 0 está representado por la suma vacía .
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 entero x , el n- ésimo dígito es 1 si F −n aparece en la suma que representa x ; ese dígito es 0 en caso contrario. Por ejemplo, 24 puede estar representado por 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 entero x está representado por una cadena de longitud impar si y solo si x > 0 .
Ver también
Referencias
- ^ Nota histórica sobre el nombre Representación de Zeckendorf por R Knott, Universidad de Surrey
- ^ Knuth, Donald E. (1988). "Multiplicación de Fibonacci" (PDF) . Letras de matemáticas aplicadas . 1 (1): 57–60. doi : 10.1016 / 0893-9659 (88) 90176-0 . ISSN 0893-9659 . Zbl 0633.10011 .
- ^ Knuth, Donald (11 de diciembre de 2008). Números de Negafibonacci y el plano hiperbólico . Reunión anual, Asociación Matemática de América. El hotel Fairmont, San José, CA.
enlaces externos
- Weisstein, Eric W. "Teorema de Zeckendorf" . MathWorld .
- Weisstein, Eric W. "Representación de Zeckendorf" . MathWorld .
- Teorema de Zeckendorf en cortar el nudo
- GM Phillips (2001) [1994], "Representación 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 de Zeckendorf de un entero positivo es única en PlanetMath , que está bajo la licencia Creative Commons Attribution / Share-Alike License .