Teorema de Zeckendorf
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:
- Existência: todo número inteiro positivo tem uma representação de Zeckendorf.
- 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
- ↑ Historical note on the name Zeckendorf Representation by R Knott, University of Surrey
- ↑ 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
- ↑ 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]- Weisstein, Eric W. «Zeckendorf's Theorem». MathWorld (em inglês)
- Weisstein, Eric W. «Zeckendorf Representation». MathWorld (em inglês)
- Zeckendorf's theorem em cut-the-knot
- G.M. Phillips (2001), «Zeckendorf representation», in: Hazewinkel, Michiel, Enciclopédia de Matemática, ISBN 978-1-55608-010-4 (em inglês), Springer
- OEIS - Sequência A101330 (produto Fibonacci (ou círculo) de Knuth)
Este artigo incorpora material de proof that the Zeckendorf representation of a positive integer is unique do PlanetMath, que é licenciado sob GFDL.