RPM 53 - Números de Fibonacci

Prévia do material em texto

Números de Fibonacci e representação de números inteiros positivos
 
Márcia R. Cerioli
Universidade Federal do Rio de Janeiro
cerioli@cos.ufrj.br 
  
     Introdução
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.
     Representação de números inteiros positivos
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
mailto:lenimar@mat.ufpb.br
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.
     Multiplicando números inteiros usando Fibonacci
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.
     Por que o método funciona?
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.
     Teorema de Zeckendorf
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].
     Representação de números inteiros positivos
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,
Olhando Mais de Cima         
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.
     Prova do teorema
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 , suponha (indutivamente) que todo inteiro positivomenor 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 N Fn+1, o qual é sempre possível encontrar, pois a
seqüência de Fibonacci é uma seqüência estritamente crescente de números naturais.
Logo, N = Fn+ k, onde k é um inteiro tal que (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.
A decomposição é única, pois, dado N com Fn N < Fn+1, suponha por absurdo que existam duas tais decomposições.
Completando com zeros se necessário, teríamos duas seqüências binárias a e b distintas tais que:
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 Fk. Por outro lado,
 b2F2 + ... + bk-1Fk-1 Fk-1 + Fk-3 + ... + Fa = Fk-1 < Fk,   onde   a = 3, se   k   for par, ou  a = 2, se k for ímpar, o que estabelece uma
contradição.
Para justificar a desigualdade
b2F2 + ... + bk-1Fk-1 Fk-1 + Fk-3 + ... + Fa, vamos nos concentrar primeiro na soma das duas últimas parcelas do lado
esquerdo, isto é:
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-3 Fk-3, e assim sucessivamente.
     Comentários finais
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.
 [2] GRAHAM, R. L.; KNUTH, D. E. ; PATASHNIK, O. Matemática Concreta: fundamentos para a ciência da computação. 2a edição, Rio de Janeiro: LTC, 1995.
 [3] VOROB'EV N. N. Fibonacci numbers. Londres: Pergamon, 1961.