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.

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

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

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

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

$64=55+8+1$.

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

$64=34+21+8+1$

$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. 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 $n$ tem uma representação de Zeckendorf.
2. Unicidade: nenhum número inteiro positivo $n$ tem duas representações de Zeckendorf diferentes.

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

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

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

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

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

Multiplicação de Fibonacci

Pode-se definir a seguinte operação $a\circ b$ em números naturais $a$, $b$: dadas as representações de Zeckendorf $a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)$ e $b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)$ nós definimos o produto de Fibonacci $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 é $F_{3}$, e a representação de Zeckendorf de 4 é $F_{4}+F_{2}$ ($F_{1}$ não é permitido em representações), então $2\circ 4=F_{3+4}+F_{3+2}=13+5=18.$

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

Representação com números negafibonacci

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

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

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

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

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:

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

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