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 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 alto. Las bandas verticales tienen un ancho de 10.

En matemáticas , el teorema de Zeckendorf , que lleva el nombre del 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 cada número 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 cualquier número entero positivo, existen números 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 enésimo número ^de Fibonacci. Esta suma se llama representación de Zeckendorf de N. La codificación 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 .

Hay otras formas de representar 64 como suma de 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 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, Gerrit Lekkerkerker había publicado el mismo resultado 20 años antes . ^[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 de Zeckendorf.
2. Unicidad : ningún entero positivo n tiene dos representaciones de 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 considere b = n − F _j  . Dado que b < n , b tiene una representación de Zeckendorf según 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 del número de Fibonacci en la última igualdad), por lo que la representación Zeckendorf de b no contiene F _{j  − 1}  y, por tanto, tampoco contiene F _j  . Como resultado, n puede representarse como la suma de F _j y la representación de Zeckendorf de b , de modo que los números de Fibonacci involucrados en la suma sean distintos.

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 no consecutivos que tengan la misma suma ,. Considere conjuntos y que son iguales y de los cuales se han eliminado los elementos comunes (es decir, y ). Dado que y tenía la misma suma, hemos eliminado exactamente los elementos de ambos conjuntos y también debemos tener 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 está vacío. Supongamos lo contrario, i. mi. eso y son ambos no vacíos y deje que el miembro más grande de sea F _s y el miembro más grande de sea F _t . Debido a que y no contienen elementos comunes, F _s ≠ F _t . Sin _pérdida de generalidad _, supongamos Fs < Ft . Luego 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 cualquiera de ellos debe estar vacío. ${\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'}$

Ahora supongamos (nuevamente sin pérdida de generalidad) que está vacío. Entonces tiene suma 0, y también debe ser . Pero como sólo puede contener números enteros positivos, también debe estar vacío. Para concluir: lo que implica demostrar que cada representación de Zeckendorf es única. ${\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 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 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 hecho sorprendente de que esta operación también es asociativa . ^[2]

Representación con números negafibonacci

La secuencia de Fibonacci se puede extender al índice negativo  n usando 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 ^[3] como una suma de números negafibonacci en los 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 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 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 está representado por una cadena de longitud impar si y sólo si x > 0 .

Ver también

• secuencia completa
• Codificación de Fibonacci
• 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. Knuth, Donald E. (1988). "Multiplicación de Fibonacci" (PDF) . Letras de Matemática Aplicada . 1 (1): 57–60. doi : 10.1016/0893-9659(88)90176-0 . ISSN  0893-9659. Zbl  0633.10011.
3. 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.

• 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 prueba de que la representación Zeckendorf de un número entero positivo es única en PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .