direita|miniaturadaimagem|267x267px|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 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.Historical note on the name Zeckendorf Representation by R Knott, University of Surrey Como tal, o teorema é um exemplo da Lei de Stigler.

Prova 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 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.

Representação com números negafibonacci 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 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 .

Ligações externas

Zeckendorf's theorem em cut-the-knot

Categoria:Teoremas na teoria dos números