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 ${\displaystyle N}$ for qualquer inteiro positivo, existem inteiros positivos ${\displaystyle c_{i}\geq 2}$, com ${\displaystyle c_{i+1}>c_{i}+1}$, de modo que

${\displaystyle N=\sum _{i=0}^{k}F_{c_{i}},}$

onde ${\displaystyle F_{n}}$ é o enésimo número de Fibonacci. Essa soma é chamada de representação de Zeckendorf de ${\displaystyle N}$. A codificação de Fibonacci de ${\displaystyle N}$ pode ser derivada de sua representação de Zeckendorf.

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

${\displaystyle 64=55+8+1}$.

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

${\displaystyle 64=34+21+8+1}$

${\displaystyle 64=55+5+3+1}$

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.^[1] Como tal, o teorema é um exemplo da Lei de Stigler.

Prova

O teorema de Zeckendorf tem duas partes:

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

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

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 é ${\displaystyle F_{j}}$ é estritamente menor do que o próximo número de Fibonacci maior ${\displaystyle F_{j+1}}$.

O lema pode ser provado por indução em ${\displaystyle j}$.

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

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

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

Multiplicação de Fibonacci

Pode-se definir a seguinte operação ${\displaystyle a\circ b}$ em números naturais ${\displaystyle a}$, ${\displaystyle b}$: dadas as representações de Zeckendorf ${\displaystyle a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)}$ e ${\displaystyle b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)}$ nós definimos o produto de Fibonacci ${\displaystyle a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}.}$

Por exemplo, a representação de Zeckendorf de 2 é ${\displaystyle F_{3}}$, e a representação de Zeckendorf de 4 é ${\displaystyle F_{4}+F_{2}}$ (${\displaystyle F_{1}}$ não é permitido em representações), então ${\displaystyle 2\circ 4=F_{3+4}+F_{3+2}=13+5=18.}$

(O produto nem sempre está na forma de Zeckendorf. Por exemplo, ${\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}.}$)

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

A sequência de Fibonacci pode ser estendida para o índice negativo ${\displaystyle n}$ usando a relação de recorrência reorganizada

${\displaystyle F_{n-2}=F_{n}-F_{n-1},}$

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

${\displaystyle F_{-n}=(-1)^{n+1}F_{n}.}$

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:

• ${\displaystyle -11=F_{-4}+F_{-6}=(-3)+(-8)}$
• ${\displaystyle 12=F_{-2}+F_{-7}=(-1)+13}$
• ${\displaystyle 24=F_{-1}+F_{-4}+F_{-6}+F_{-9}=1+(-3)+(-8)+34}$
• ${\displaystyle -43=F_{-2}+F_{-7}+F_{-10}=(-1)+13+(-55)}$
• ${\displaystyle 0}$ é representado pela soma vazia.

${\displaystyle 0=F_{-1}+F_{-2}}$, 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 ${\displaystyle x}$, o enésimo dígito é ${\displaystyle 1}$ se ${\displaystyle F_{-n}}$ aparecer na soma que representa ${\displaystyle x}$; esse dígito é ${\displaystyle 0}$ caso contrário. Por exemplo, ${\displaystyle 24}$ pode ser representado pela string ${\displaystyle 100101001}$, que tem o dígito ${\displaystyle 1}$ nas casas ${\displaystyle 9}$, ${\displaystyle 6}$, ${\displaystyle 4}$ e ${\displaystyle 1}$, porque ${\displaystyle 24=F_{-1}+F_{-4}+F_{-6}+F_{-9}}$. O inteiro ${\displaystyle x}$ é representado por uma string de comprimento ímpar se e somente se ${\displaystyle x>0}$.

Referências

• 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  !CS1 manut: Língua não reconhecida (link)

Ligações externas

• Weisstein, Eric W. «Zeckendorf's Theorem» (em inglês). MathWorld 
• Weisstein, Eric W. «Zeckendorf Representation» (em inglês). MathWorld 
• 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.

• Portal da matemática