Os números de Fibonacci constituem a base matemática de toda a Natureza e talvez o vestígio mais importante para compreendermos que fomos todos formados da mesma coisa, seja ela o Criador, seja ela a força fractal dos universos. a prova de algo além de todos nós.

Número de Fibonacci

Na matemática, os Números de Fibonacci são uma sequência (sucessão, em Portugal) definida como recursiva pela fórmula abaixo:

vide as fórmulas no link: http://pt.wikipedia.org/wiki/N%C3%BAmero_de_Fibonacci

Na prática: você começa com 0 e 1, e então produz o próximo número de Fibonacci somando os dois anteriores para formar o próximo. Os primeiros Números de Fibonacci (sequência A000045 na OEIS) para n = 0, 1,… são

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946…
Esta sequência foi descrita primeiramente por Leonardo de Pisa, também conhecido como Fibonacci (Dc. 1200), para descrever o crescimento de uma população de coelhos. Os números descrevem o número de casais em uma população de coelhos depois de n meses se for suposto que:

no primeiro mês nasce apenas um casal,
casais amadurecem sexualmente (e reproduzem-se) apenas após o segundo mês de vida,
não há problemas genéticos no cruzamento consanguíneo,
todos os meses, cada casal fértil dá a luz a um novo casal, e
os coelhos nunca morrem.
O termo sequência de Fibonacci é também aplicado mais genericamente a qualquer função g onde g(n + 2) = g(n) + g(n + 1). Estas funções são precisamente as de formato g(n) = aF(n) + bF(n + 1) para alguns números a e b, então as sequências de Fibonacci formam um espaço vetorial com as funções F(n) e F(n + 1) como base.

Em particular, a sequência de Fibonacci com F(1) = 1 e Ver artigo principal: Sequência de Fibonacci F(2) = 3 é conhecida como os números de Lucas. A importância dos números de Lucas L(n) reside no fato deles gerarem a Proporção áurea para as enésimas potências:


Os números de Lucas se relacionam com os de Fibonacci pela fórmula:

L(n) = F(n - 1) + F(n + 1)
Com esta fórmula podemos montar a Sequência de Fibonacci e descobrir, por exemplo, quantos coelhos foram gerados no sexto mês, basta aplicar a fórmula descrita acima até chegar ao ponto inicial de 1 e 1.

Como mostra a figura abaixo;


Ou seja, no sexto mês foram gerados 8 coelhos

F(6) = (F(6) - 1) + (F(6) - 2) = 5 e 4 ? 8 ( Soma do Resultado de F(5) e F(4) )
F(5) = (F(5) - 1) + (F(5) - 2) = 4 e 3 ? 5 ( Soma do Resultado de F(4) e F(3) )
F(4) = (F(4) - 1) + (F(4) - 2) = 3 e 2 ? 3 ( Soma do Resultado de F(3) e F(2) )
F(3) = (F(3) - 1) + (F(3) - 2) = 2 e 1 ? 2
F(2) = (F(2) - 1) + (F(2) - 2) = 1 e 0 ? 1

e a primeira posição 1.

Note que a Sequência de Fibonacci esta no resultado de cada posição; 1,1,2,3,5,8 …

Fórmula explícita

Conforme mencionado por Johannes Kepler, a taxa de crescimento dos números de Fibonacci, que é F(n + 1) /F(n), tende à Proporção áurea, denominada ?. Esta é a raiz positiva da equação de segundo grau x² ? x ? 1 = 0, então ?² = ? + 1. Se multiplicarmos ambos os lados por ?n, teremos ?n+2 = ?n+1 + ?n, então a função ?n é uma sequência de Fibonacci. É possível demonstrar que a raiz negativa da mesma equação, 1 ? ?, tem as mesmas propriedades, então as duas funções ?n e (1 ? ?)n formam outra base para o espaço.

Ajustando os coeficientes para obter os valores iniciais adequados F(0) = 0 e F(1) = 1, temos a fórmula de Binet


Este resultado também pode ser derivado utilizando-se a técnica de gerar funções, ou a técnica de resolver relações de multiplicação


Quando n tende a infinito, o segundo termo tende a zero, e os números de Fibonacci tendem à exponencial ?n/?5. O segundo termo já começa pequeno o suficiente para que os números de Fibonacci possam ser obtidos usando somente o primeiro termo arredondado para o inteiro mais próximo.

Calculando números de Fibonacci

Na prática não é conveniente calcular os números de Fibonacci usando potências da proporção áurea, a não ser para valores pequenos de n, já que os erros de arredondamento se acumulam e a precisão dos números de ponto flutuante normalmente não será suficiente.

A implementação direta da definição recursiva da sequência de Fibonacci também não é recomendável porque os mesmos valores são calculados muitas vezes (a não ser que a linguagem de programação guarde automaticamente os valores calculados nas chamadas anteriores da mesma função com o mesmo argumento). Por esse motivo, normalmente calcula-se os números de Fibonacci "de baixo para cima", começando com os dois valores 0 e 1, e depois repetidamente substituindo-se o primeiro número pelo segundo, e o segundo número pela soma dos dois anteriores.

Para argumentos muito grandes, quando utiliza-se um computador bignum, é mais fácil calcular os números de Fibonacci usando a seguinte equação matricial:


onde a potência de n é calculada elevando-se a matriz ao quadrado repetidas vezes.

Um exemplo de aplicação desta expressão matricial é na demonstração do teorema de Lamé sobre o algoritmo de Euclides para o cálculo do MDC. Veja por exemplo o capítulo Máximo divisor comum do Wikilivro de Teoria de números.

A seguir, um algoritmo desenvolvido em Java, o qual imprime o número de termos da sequência, determinado pela variável "x".

Fonte: Wikipedia