Mostrar código-fonte de Teorema de Zeckendorf

[[Ficheiro:Zeckendorf_representations_89px.svg|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]] [[Belgas|belga]] [[Édouard Zeckendorf]], é um [[teorema]] sobre a representação de [[Número inteiro|inteiros]] como somas de [[números de Fibonacci]].

O teorema de Zeckendorf afirma que todo número [[Números naturais|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 <math>N</math> for qualquer inteiro positivo, existem inteiros positivos <math>c_i \geq 2</math>, com <math>c_{i + 1}> c_i + 1</math>, de modo que

: <math>N = \sum_{i = 0}^k F_{c_i},</math>

onde <math>F_n</math> é o enésimo número de Fibonacci. Essa soma é chamada de '''representação de Zeckendorf''' de <math>N</math>. A codificação de Fibonacci de <math>N</math> pode ser derivada de sua representação de Zeckendorf.

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

: <math>64 = 55 + 8 + 1</math>.

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

: <math>64 = 34 + 21 + 8 + 1</math>
: <math>64 = 55 + 5 + 3 + 1</math>

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|homônimo]] que publicou seu artigo em 1972, o mesmo resultado foi publicado 20 anos antes por [[Gerrit Lekkerkerker]].<ref>[http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html#section4.2 Historical note on the name Zeckendorf Representation by R Knott, University of Surrey]</ref> 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 <math>n</math> tem uma representação de Zeckendorf.
# '''Unicidade''': nenhum número inteiro positivo <math>n</math> tem duas representações de Zeckendorf diferentes.

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

A segunda parte do teorema de Zeckendorf (unicidade) requer o seguinte [[Lema (matemática)|lema]]:

: ''Lema'': A soma de qualquer [[conjunto]] não vazio de números de Fibonacci distintos e não consecutivos cujo maior membro é <math>F_j</math> é estritamente menor do que o próximo número de Fibonacci maior <math>F_{j + 1}</math>.

O lema pode ser provado por indução em <math>j</math>.

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

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

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

== Multiplicação de Fibonacci ==
Pode-se definir a seguinte operação <math>a\circ b</math> em números naturais <math>a</math>, <math>b</math>:  dadas as representações de Zeckendorf <math>a=\sum_{i=0}^kF_{c_i}\;(c_i\ge2)</math> e <math>b=\sum_{j=0}^lF_{d_j}\;(d_j\ge2)</math> nós definimos o '''produto de Fibonacci''' <math>a\circ b=\sum_{i=0}^k\sum_{j=0}^lF_{c_i+d_j}.</math>

Por exemplo, a representação de Zeckendorf de 2 é <math>F_3</math>, e a representação de Zeckendorf de 4 é <math>F_4 + F_2</math> (<math>F_1</math> não é permitido em representações), então <math>2 \circ 4 = F_{3+4} + F_{3+2} = 13 + 5 = 18.</math>

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

Um simples rearranjo de somas mostra que esta é uma [[Comutatividade|operação comutativa]]; no entanto, [[Donald Knuth]] provou o fato surpreendente de que esta operação também é [[Associatividade|associativa]].<ref>{{citar periódico|primeiro =Donald E. |último =Knuth |autorlink =Donald Knuth |título=Fibonacci multiplication |periódico=Applied Mathematics Letters |volume=1 |número=1 |ano=1988 |páginas=57–60 |doi=10.1016/0893-9659(88)90176-0 |zbl=0633.10011 |issn=0893-9659 |url=http://www.cs.umb.edu/~rvetro/vetroBioComp/compression/FIBO/KnuthFibb.pdf}}</ref>

== Representação com números ''negafibonacci'' ==
A sequência de Fibonacci pode ser estendida para o índice negativo <math>n</math> usando a [[relação de recorrência]] reorganizada

: <math>F_{n-2} = F_n - F_{n-1}, </math>

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

: <math>F_{-n} = (-1)^{n+1} F_n. </math>

Qualquer número inteiro pode ser representado de forma única<ref>{{citar conferência|último =Knuth |primeiro =Donald |autorlink =Donald Knuth |url=http://www.allacademic.com/meta/p206842_index.html |título=Negafibonacci Numbers and the Hyperbolic Plane |data=2008-12-11 |local=The Fairmont Hotel, San Jose, CA |conferencia=Annual meeting, Mathematical Association of America}}</ref> como uma soma de números negafibonacci em que não são usados dois números negafibonacci consecutivos. Por exemplo:

* <math>-11 = F_{-4} + F_{-6} = (-3) + (-8)</math>
* <math>12 = F_{-2} + F_{-7} = (-1) + 13</math>
* <math>24 = F_{-1} + F_{-4} + F_{-6} + F_{-9} = 1 + (-3) + (-8) + 34</math>
* <math>-43 = F_{-2} + F_{-7} + F_{-10} = (-1) + 13 + (-55)</math>
* <math>0</math> é representado pela [[soma vazia]].

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

{{Referências}}

* {{citar periódico|zbl=0252.10011 |último =Zeckendorf |primeiro =E. |título=Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas |língua=fr |periódico=Bull. Soc. R. Sci. Liège |volume=41 |páginas=179–182 |ano=1972 |issn=0037-9565}}

== Ligações externas ==

* {{MathWorld|title=Zeckendorf's Theorem|urlname=ZeckendorfsTheorem}}
* {{MathWorld|title=Zeckendorf Representation|urlname=ZeckendorfRepresentation}}
* [http://www.cut-the-knot.org/ctk/OnePile.shtml#fibnim Zeckendorf's theorem] em [[cut-the-knot]]
* {{SpringerEOM|urlname=Z/z120020|title=Zeckendorf representation|author=G.M. Phillips}}
* {{URL|https://oeis.org/A101330|OEIS - Sequência A101330 (produto Fibonacci (ou círculo) de Knuth)}}

{{PlanetMath attribution|id=8810|title=proof that the Zeckendorf representation of a positive integer is unique}}
{{Portal3|matemática}}
[[Categoria:Teoremas na teoria dos números]]