Sequencia Fibona CCI

SEQÜÊNCIA DE FIBONACCI
Cícero Thiago B. Magalhães

Nível Avançado

INTRODUÇÃO
O nome seqüência de Fibonacci, foi dado pelo matemático francês Edouard Lucas no século XIX. Porém, a seqüência surgiu de um problema que estava proposto na obra "Liber Abaci" de Leonardo de Pisa (1180 – 1250), conhecido como Fibonacci. O problema era o seguinte: "Um homem põe um casal de coelhos dentro de um cercado. Quantos pares de coelhos serão produzidos em um ano, se a natureza desses coelhos é tal que a cada mês um casal gera um novo casal, que se torna fértil a partir do segundo mês?" Depois de séculos de trabalho, é possível hoje citar uma quantidade enorme de propriedades da seqüência do número de coelhos existentes após n meses. O objetivo deste trabalho é apresentar algumas propriedades básicas desta seqüência.

Definição
A seqüência de Fibonacci é definida da seguinte maneira: e ,
Por conveniência, algumas vezes usaremos

Propriedades básicas
(I) Para todo
Prova:
Vamos supor e

(II) Se e então
Prova: Vamos fazer indução sobre m: (verdadeira) (verdadeira)
Seja q > 2 e suponhamos a propriedade válida para todo e para todo n > 1. Esta suposição, mais o fato de que a propriedade vale também para k = 1, nos garante:

Somando membro a membro essas igualdades e levando em consideração a fórmula recursiva que define

Ou seja, a fórmula vale também para q, sempre que n > 1. O princípio da indução nos garante então que vale para todo e qualquer n > 1.
(III) Dois números de Fibonacci consecutivos e são primos entre si.
A prova fica como exercício.
(IV) Se então
Prova: Por hipótese n = mq, para algum Usaremos indução sobre r.
Se q = 1, então m = n e é fácil ver que Seja e admitamos que
Então, usando a propriedade (II):

Como e (pois, pela hipótese de indução, fm divide então divide a soma desses dois produtos. Ou seja:
(V) Seja d = mdc(m, n), então mdc
Prova: Indução em m + n. Se m = 1, mdc(m, n) = 1 e mdc(fm,