(F(2) - 2) = 1 e 0 1e a primeira posicao 1.Note que a Sequencia de Fibonacci esta no resultado de cada posicao: 1, 1, 2, 3, 5, 8, ... Representacoes alternativasPara analizar a sequencia de Fibonacci (e, em geral, quaisquer sequencias) e conveniente obter outras maneiras de representa-la matematicamente. Funcao geradoraUma funcao geradora para uma sequencia qualquer e a funcaoou seja, uma serie potencias formais em que cada coeficiente e um elemento da sequencia. Os numeros de Fibonacci possuem a seguinte funcao geradoraQuando se expande esta funcao em potencias de , os coeficientes sao justamente os termos da sequencia de Fibonacci: Formula explicitaConforme mencionado por Johannes Kepler, a taxa de crescimento dos numeros de Fibonacci, que e F(n + 1) /F(n), tende a Proporcao aurea, denominada . Esta e a raiz positiva da equacao de segundo grau x2 x 1 = 0, entao 2 = + 1. Se multiplicarmos ambos os lados por n, teremos n+2 = n+1 + n, entao a funcao n e uma sequencia de Fibonacci. E possivel demonstrar que a raiz negativa da mesma equacao, 1 , tem as mesmas propriedades, entao as duas funcoes n e (1 )n formam outra base para o espaco.Ajustando os coeficientes para obter os valores iniciais adequados F(0) = 0 e F(1) = 1, tem-se a formula de Binet:Este resultado tambem pode ser derivado utilizando-se a tecnica de funcoes geradoras, ou a tecnica de resolver relacoes de recorrencia.Quando n tende a infinito, o segundo termo tende a zero, e os numeros de Fibonacci tendem a exponencial n/5. O segundo termo ja comeca pequeno o suficiente para que os numeros de Fibonacci possam ser obtidos usando somente o primeiro termo arredondado para o inteiro mais proximo. Forma matricialPara argumentos muito grandes, quando utiliza-se um computador bignum, e mais facil calcular os numeros de Fibonacci usando a seguinte equacao matricial:em que a potencia de n e calculada elevando-se a matriz ao quadrado repetidas vezes.Um exemplo de aplicacao desta expressao matricial e na demonstracao do teorema de Lame sobre o algoritmo de Euclides para o calculo do MDC.Representacao da Serie de Fibonacci na Molle Antonelliana em Turim, Italia. Tipos de algoritmosHa diversos algoritmos (metodos) para calcular o -esimo elemento da sequencia de Fibonacci, sendo que os mais comuns empregam um das seguintes abordagens:RecursivaIterativaDividir para conquistarA seguir e apresentado um exemplo de cada um destes tipos de algoritmos em pseudocodigo. Abordagem recursivaA propria definicao da sequencia de Fibonacci pode ser tomada como base para implementar um algoritmo recursivo que gera os termos da sequencia, como e mostrado a seguir: funcao se entaoretorne caso contrarioretorne Apesar de simples, essa estrategia nao e recomendavel porque os mesmos valores sao calculados muitas vezes (a nao ser que a linguagem de programacao guarde automaticamente os valores calculados nas chamadas anteriores da mesma funcao com o mesmo argumento). Uma analise cuidadosa mostra que a complexidade computacional do algoritmo e . Por esse motivo, normalmente calcula-se os numeros de Fibonacci "de baixo para cima",comecando com os dois valores 0 e 1, e depois repetidamente substituindo-se o primeiro numero pelo segundo, e