Teorema de Zeckendorf

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa
Os primeiros 89 números naturais na forma de Zeckendorf. Cada altura e largura dos retângulos é um número de Fibonacci. As faixas verticais têm largura 10

O teorema de Zeckendorf, em homenagem ao matemático belga Édouard Zeckendorf, é um teorema sobre a representação de inteiros como somas de números de Fibonacci.

O teorema de Zeckendorf afirma que todo número inteiro positivo pode ser representado exclusivamente como a soma de um ou mais números de Fibonacci distintos, de forma que a soma não inclua dois números de Fibonacci consecutivos. Mais precisamente, se for qualquer inteiro positivo, existem inteiros positivos , com , de modo que

onde é o enésimo número de Fibonacci. Essa soma é chamada de representação de Zeckendorf de . A codificação de Fibonacci de pode ser derivada de sua representação de Zeckendorf.

Por exemplo, a representação de Zeckendorf de 64 é

.

Existem outras maneiras de representar 64 como a soma dos números de Fibonacci – por exemplo

mas essas não são representações de Zeckendorf porque 34 e 21 são números de Fibonacci consecutivos, assim como 5 e 3.

Para qualquer inteiro positivo dado, uma representação que satisfaça as condições do teorema de Zeckendorf pode ser encontrada usando um algoritmo guloso, escolhendo o maior número de Fibonacci possível em cada estágio.

História[editar | editar código-fonte]

Embora o teorema tenha o nome do autor homônimo que publicou seu artigo em 1972, o mesmo resultado foi publicado 20 anos antes por Gerrit Lekkerkerker.[1] Como tal, o teorema é um exemplo da Lei de Stigler.

Prova[editar | editar código-fonte]

O teorema de Zeckendorf tem duas partes:

  1. Existência: todo número inteiro positivo tem uma representação de Zeckendorf.
  2. Unicidade: nenhum número inteiro positivo tem duas representações de Zeckendorf diferentes.

A primeira parte do teorema de Zeckendorf (existência) pode ser provada por indução. Para é claramente verdade (já que esses são números de Fibonacci), para temos . Se for um número de Fibonacci, não há o que provar. Caso contrário, existe tal que . Agora suponha que cada tenha uma representação de Zeckendorf (hipótese de indução) e considere . Como , tem uma representação de Zeckendorf. Ao mesmo tempo, , então a representação de Zeckendorf de não contém . Como resultado, pode ser representado como a soma de e a representação de Zeckendorf de .

A segunda parte do teorema de Zeckendorf (unicidade) requer o seguinte lema:

Lema: A soma de qualquer conjunto não vazio de números de Fibonacci distintos e não consecutivos cujo maior membro é é estritamente menor do que o próximo número de Fibonacci maior .

O lema pode ser provado por indução em .

Agora pegue dois conjuntos não vazios de números de Fibonacci distintos não consecutivos e que tenham a mesma soma. Considere os conjuntos e que são iguais a e dos quais os elementos comuns foram removidos (ou seja, e ). Uma vez que e tiveram soma igual, removemos exatamente os elementos de de ambos os conjuntos, e devem ter a mesma soma também.

Agora mostraremos por contradição que pelo menos um entre e está vazio. Assuma o contrário, ou seja, que e são ambos não vazios e que o maior membro de é e o maior membro de é . Como e não contêm elementos comuns, . Sem perda de generalidade, suponha que . Então, pelo lema, a soma de é estritamente menor que e, portanto, estritamente menor que , enquanto a soma de é claramente pelo menos . Isso contradiz o fato de que e têm a mesma soma, e podemos concluir que ou deve estar vazio.

Agora assuma (novamente sem perda de generalidade) que está vazio. Então tem soma 0, e então . Mas como só pode conter inteiros positivos, também deve estar vazio. Para concluir: o que implica , provando que cada representação de Zeckendorf é única.

Multiplicação de Fibonacci[editar | editar código-fonte]

Pode-se definir a seguinte operação em números naturais , : dadas as representações de Zeckendorf e nós definimos o produto de Fibonacci

Por exemplo, a representação de Zeckendorf de 2 é , e a representação de Zeckendorf de 4 é ( não é permitido em representações), então

(O produto nem sempre está na forma de Zeckendorf. Por exemplo, )

Um simples rearranjo de somas mostra que esta é uma operação comutativa; no entanto, Donald Knuth provou o fato surpreendente de que esta operação também é associativa.[2]

Representação com números negafibonacci[editar | editar código-fonte]

A sequência de Fibonacci pode ser estendida para o índice negativo usando a relação de recorrência reorganizada

que produz a sequência de números "negafibonacci" que satisfazem

Qualquer número inteiro pode ser representado de forma única[3] como uma soma de números negafibonacci em que não são usados dois números negafibonacci consecutivos. Por exemplo:

  • é representado pela soma vazia.

, por exemplo, a exclusividade da representação depende da condição de que não sejam usados dois números negafibonacci consecutivos.

Isso dá um sistema de códigos inteiros, semelhante à representação do teorema de Zeckendorf. Na string que representa o inteiro , o enésimo dígito é se aparecer na soma que representa ; esse dígito é caso contrário. Por exemplo, pode ser representado pela string , que tem o dígito nas casas , , e , porque . O inteiro é representado por uma string de comprimento ímpar se e somente se .

Referências

  1. Historical note on the name Zeckendorf Representation by R Knott, University of Surrey
  2. Knuth, Donald E. (1988). «Fibonacci multiplication» (PDF). Applied Mathematics Letters. 1 (1): 57–60. ISSN 0893-9659. Zbl 0633.10011. doi:10.1016/0893-9659(88)90176-0 
  3. Knuth, Donald (11 de dezembro de 2008). Negafibonacci Numbers and the Hyperbolic Plane. Annual meeting, Mathematical Association of America. The Fairmont Hotel, San Jose, CA 
  • Zeckendorf, E. (1972). «Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas». Bull. Soc. R. Sci. Liège (em French). 41: 179–182. ISSN 0037-9565. Zbl 0252.10011 

Ligações externas[editar | editar código-fonte]

Este artigo incorpora material de proof that the Zeckendorf representation of a positive integer is unique do PlanetMath, que é licenciado sob GFDL.