 |
|
|
|||
 |
|||||
| |
|
|
|||
| |
|||||
Os números de Fibonacci, que são os termos da famosa seqüência de números inteiros positivos, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... são bem conhecidos e estudados. Essa seqüência é definida pela relação de recorrência Fn = Fn-1 + Fn-2, n > 2 com F1 = 1 e F2 = 1, e tem sua origem no problema da reprodução de coelhos, descrito no Liber Abaci, escrito por Leonardo de Pisa, o Fibonacci, em 1202. (Ver RPM 17, p. 4, e RPM 24, p. 32.) Nosso objetivo é divulgar uma propriedade dos números de Fibonacci muito pouco conhecida entre nós, a saber: Todo número inteiro positivo pode ser escrito de maneira única como soma de números de Fibonacci distintos e não consecutivos. Por exemplo, o número 16 pode ser obtido de várias maneiras como soma de números de Fibonacci, entre elas: 16 = 8 + 8, 16 = 8 + 5 + 3 ou 16 = 13 + 3. Na primeira, os números não são distintos; na segunda, são distintos porém consecutivos. Somente na terceira temos números de Fibonacci distintos e não consecutivos: 13 = F7 e 3 = F4. O Teorema de Zeckendorf ([1] e [2]), como também é conhecida a propriedade descrita acima, garante que 13 + 3 é a única maneira de escrever 16 como soma de números de Fibonacci distintos e não consecutivos. A propriedade vale para qualquer número inteiro positivo. Nosso propósito é dar uma descrição do teorema e sua prova e examinar brevemente algumas de suas conseqüências.
Dado um número inteiro positivo N, decompor N em números de Fibonacci consiste em escrever N como soma de números de Fibonacci distintos. Cada soma de números de Fibonacci distintos obtida por esse processo é chamada uma decomposição de N. Como já vimos, 16 = 8 + 5 + 3 = 13 + 3 são decomposições de 16. A tabela a seguir lista os primeiros números de Fibonacci e nos ajuda a visualizar as possibilidades para uma decomposição de números pequenos.
Vamos agora mostrar como podemos representar decomposições por seqüências binárias finitas, isto é, seqüências cujos termos são 0 e 1. Por exemplo, 10 = 8 + 2 = F6 + F3 = 1F6 + 0F5 + 0F4 + 1F3 + 0F2, onde 1 indica que o respectivo número de Fibonacci ocorre na decomposição e 0 indica o contrário. Neste caso, a seqüência binária é dada por (0, 1, 0, 0, 1). Na prática, costuma-se denotar 10 = (10010)F. A notação (.)F segue o mesmo padrão utilizado na representação de números naturais em base 10 ou 2, isto é, da direita para a esquerda, e zeros a esquerda não são escritos. Dada uma decomposição de N, sempre é possível determinar k tal que Fk é o maior número de Fibonacci utilizado na decomposição de números binários a2, a3, ..., ak, tais que N = a2F2 + a3F3 + ... + akFk. A razão para F1 não ser incluído está no fato que estamos interessados em números de Fibonacci distintos e F1 = F2 = 1, logo somente um deles pode ser usado. A decomposição em números de Fibonacci pode não ser única, como já vimos no caso N = 16. Para obter a unicidade, não são utilizados, na decomposição, dois números de Fibonacci consecutivos. Isso pode ser feito, pois a soma de dois números de Fibonacci consecutivos é exatamente o próximo número de Fibonacci. Assim, poderemos sempre substituir os termos de uma decomposição de modo a obter uma decomposição desse tipo, isto é, podemos sempre substituir ocorrências de ...011... por ocorrências de ...100... em uma decomposição. Essa substituição é feita da esquerda para a direita, de modo a eliminar todos os 1's consecutivos. Todas as medidas acima foram tomadas na tentativa de elaborar um conjunto de regras que permitam decompor de uma única maneira cada número natural em soma de números de Fibonacci distintos. Se isso for realmente possível para todo número inteiro positivo, a decomposição estabelecerá uma correspondência e será uma representação, sendo que números inteiros poderão ser vistos como seqüências de números binários sem 1's consecutivos. E é exatamente isso que o Teorema de Zeckendorf estabelece. Mas, antes, vamos brincar um pouco com essa decomposição de inteiros.
A decomposição de números como soma de números de Fibonacci pode ser usada em um método que permite multiplicar dois números inteiros usando adições. Por exemplo, suponha que desejamos multiplicar 16 por 63. A idéia é construir uma tabela onde a primeira coluna é formada por 1 e um dos números, digamos 16. A segunda coluna é obtida da primeira dobrando-se os números e, a partir daí, toda coluna da tabela é obtida pela soma das duas anteriores. A tabela é construída até que na primeira linha seja atingido um número maior ou igual ao outro número, no caso, a 63. Veja a tabela abaixo:
A seguir considera-se uma decomposição de 63 em números de Fibonacci. Temos, por exemplo, 63 = 55 + 8 = F10 + F6 = (100010000)F. Para obter o produto 16 x 63 basta tomar os números correspondentes a 8 e 55 na tabela. Assim, temos 16 x 63 = 128 +880 = 1008. O processo também pode ser executado com 63 e 16 com os papéis trocados. A tabela obtida está a seguir. Observe que 16 = 13 + 3. Logo, 16 x 63 é obtido somando-se 189 com 819.
O leitor é convidado a aplicar o método a outros números antes de prosseguir.
Sejam a e b dois números inteiros positivos que desejamos multiplicar, com a = (ak ... a3a2) Na tabela temos, na primeira coluna, o par (1, b ) = (F2, F2.b). Na segunda coluna, o par (F3, F3.b) e, em cada coluna seguinte, um par Assim, temos a.b = a2bF2 + ... + akbFk que é exatamente a soma dos elementos das colunas da segunda linha correspondentes aos elementos ai = 1 na decomposição em números de Fibonacci de a. Observamos que, para usar esse método para multiplicar dois números, basta uma decomposição qualquer em números de Fibonacci de um deles, ou seja, essa decomposição não precisa ser a dada pela representação.
O resultado a seguir garante que todo número inteiro positivo tem uma decomposição em números de Fibonacci e, mais ainda, que todo número inteiro positivo tem uma representação em números de Fibonacci. Teorema de Zeckendorf Seja N um número inteiro positivo. Então existe uma única seqüência binária b = (b2, b3,...) tal que N = b2F2 + b3F3 + ... e bibi+1 = 0, para todo i > 2. Antes de provar o teorema, vamos estudar algumas propriedades da seqüência de Fibonacci que serão úteis. Outras identidades envolvendo os números de Fibonacci podem ser encontradas em [2] e [3].
As seguintes afirmações são verdadeiras: (a) F1 + F2 + ... + Fn = Fn+2 - 1. (b) F1 + F3 + ... + F2n-1 = F2n. (c) F2 + F4 + ... + F2n = F2n+1-1. Para comprovar (a) basta observar que, por definição, F1 = F3 - F2, F2 = F4 - F3, F3 = F5 - F4, ..., Fn-1 = Fn+1 - Fn e Fn = Fn+2 - Fn+1, Somando membro a membro todas as equações acima, teremos, do lado esquerdo, F1 + F2 + ... + Fn, enquanto do lado direito, devido à alternância de sinais, restam somente -F2 da primeira equação e Fn+2 da última. Como F2 = 1, temos a identidade desejada. Para comprovar (b) basta observar que F1 = F2, F3 = F4 - F2, F5 = F6 - F4, ..., F2n-1 = F2 n - F2n-2. Somando as equações, teremos, do lado esquerdo, F1 + F3 + ... + F2n-1 enquanto do lado direito, resta F2n. A comprovação de (c) é, de novo, análoga, observando que F2 = F3 - F1, F4 = F5 - F3, ..., F2n = F2n+1 - F2n-1 e F1 = 1. Considerando (b) e (c) juntas, podemos escrever (d) Fk - 1 = Fk-1 + Fk-3 + ... + Fa onde a = 3 se k é par ou a = 2 se k é ímpar. É essa propriedade que nos será útil aqui.
Primeiro, vamos provar que todo número inteiro pode ser escrito dessa forma, usando um raciocínio por indução. Se N < 4, é claro que N é ele mesmo um número de Fibonacci. Dado agora Logo, N = Fn+ k, onde k é um inteiro tal que A decomposição é única, pois,
dado N com Fn N = b2F2 +...+ bnFn = a2F2 +...+ anFn. Seja k o maior índice onde as seqüências diferem e suponha, sem perda de generalidade, que ak= 1 e bk= 0. Logo: Como ak= 1, então a2F2 + ... +akFk Para justificar a desigualdade b2F2 + ... + bk-1Fk-1 bk-2Fk-2 + ... + bk-1Fk-1. Os possíveis valores para essa soma são: Fk-1 (se bk-2 = 0 e bk-1 = 1), ou Fk-2 (se bk-2 = 1 e bk-1 = 0), ou ainda 0 (se bk-1 = bk-1 = 0). Dos três valores, o maior é Fk-1, já que a seqüência de Fibonacci é
crescente. Então,
bk-2Fk-2+ bk-1Fk-1  Fk-1. Um raciocínio análogo mostra que bk-4Fk-4+ bk-3Fk-3Fk-3, e assim sucessivamente.
Questionado se existe uma outra seqüência de números inteiros positivos que também tem esta propriedade, Daykin [1] provou que a seqüência de Fibonacci é a única seqüência de inteiros para a qual cada número inteiro positivo pode ser escrito de maneira única como soma de termos distintos e não consecutivos dessa seqüência. Referências bibliográficas [1] DAYKIN, D. E. Representation of
natural numbers as sums of generalized Fibonacci numbers. Journal
of the London Mathematical Society 35, págs. 143-160, 1960. |
, suponha (indutivamente) que todo inteiro positivo menor que
N possa ser escrito dessa forma e considere o maior número
de Fibonacci Fn que seja menor ou igual a N, isto é, Fn
(pois Fn> 0) e também k < Fn-1 (caso contrário, teríamos N = Fn+ k
Fn +Fn-1 = Fn+1, o que é falso). Se k = 0, nada mais há a ser provado. Se 
, como 
, então, pela hipótese indutiva, podemos escrever
k como soma de números de Fibonacci não consecutivos
e menores que Fn-1 (já que k < Fn-1) e, portanto, N = Fn + k também pode. Dessa forma, temos uma decomposição
de N em soma de números de Fibonacci distintos e não
consecutivos. 
.