Teorema de Zeckendorf

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 $N$ for qualquer inteiro positivo, existem inteiros positivos $c_i\ge 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 $𝑺$ e $𝑻$ que tenham a mesma soma. Considere os conjuntos ${𝑺}^{\prime }$ e ${𝑻}^{\prime }$ que são iguais a $𝑺$ e $𝑻$ dos quais os elementos comuns foram removidos (ou seja, ${𝑺}^{\prime }=𝑺\setminus 𝑻$ e ${𝑻}^{\prime }=𝑻\setminus 𝑺$). Uma vez que $𝑺$ e $𝑻$ tiveram soma igual, removemos exatamente os elementos de $𝑺\cap 𝑻$ de ambos os conjuntos, ${𝑺}^{\prime }$ e ${𝑻}^{\prime }$ devem ter a mesma soma também.

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

Agora assuma (novamente sem perda de generalidade) que ${𝑺}^{\prime }$ está vazio. Então ${𝑺}^{\prime }$ tem soma 0, e então ${𝑻}^{\prime }$. Mas como ${𝑻}^{\prime }$ só pode conter inteiros positivos, também deve estar vazio. Para concluir: ${𝑺}^{\prime }={𝑻}^{\prime }=\varnothing$ o que implica $𝑺=𝑻$, 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\ge 2)$ e $b=\sum _{j=0}^l{F}_{d_j}(d_j\ge 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$.

• Predefinição:Citar periódico

Ligações externas

• Predefinição:MathWorld
• Predefinição:MathWorld
• Zeckendorf's theorem em cut-the-knot
• Predefinição:SpringerEOM
• Predefinição:URL