o segundo numero pela soma dos dois anteriores.Uma outra alternativa e fazer uso da formula apresentada na secao anterior, que envolve potencias da proporcao aurea. No entanto, isso pode nao ser muito conveniente para valores grandes de n, ja que os erros de arredondamento se acumulam e a precisao dos numeros de ponto flutuante normalmente nao sera suficiente. Abordagem iterativaCom o uso de um algoritmo iterativo como o que e mostrado a seguir, e possivel obter a sequencia um pouco mais eficientemente:funcao para desde ate facaretorne Neste caso, a complexidade computacional do algoritmo e . Abordagem dividir para conquistarO algoritmo abaixo e bem mais eficiente e baseia-se na representacao matricial da sequencia de Fibonacci. Sua complexidade computacional e .funcao se entaoretorne enquanto facase e par entaoretorne AplicacoesOs numeros de Fibonacci sao importantes para a analise em tempo real do algoritmo euclidiano, para determinar o maximo divisor comum de dois numeros inteiros.Matiyasevich mostrou que os numeros de Fibonacci podem ser definidos por uma Equacao diofantina, o que o levou a solucao original do Decimo Problema de Hilbert.Os numeros de Fibonacci aparecem na formula das diagonais de um triangulo de Pascal (veja coeficiente binomial).Um uso interessante da sequencia de Fibonacci e na conversao de milhas para quilometros. Por exemplo, para saber aproximadamente a quantos quilometros 5 milhas correspondem, pega-se o numero de Fibonacci correspondendo ao numero de milhas (5) e olha-se para o numero seguinte (8). 5 milhas sao aproximadamente 8 quilometros. Esse metodo funciona porque, por coincidencia, o fator de conversao entre milhas e quilometros (1.609) e proximo de (1.618) (obviamente ele so e util para aproximacoes bem grosseiras: alem do factor de conversao ser diferente de , a serie converge para ).Exemplo de sons FibonacciEm musica os numeros de Fibonacci sao utilizados para a afinacao, tal como nas artes visuais, determinar proporcoes entre elementos formais. Um exemplo e a Musica para Cordas, Percussao e Celesta de Bela Bartok.Le Corbusier usou a sequencia de Fibonacci na construcao do seu modulor, um sistema de proporcoes baseadas no corpo humano e aplicadas ao projeto de arquitetura.Em The Wave Principal, Elliot defende a ideia que as flutuacoes do mercado seguem um padrao de crescimento e decrescimento que pode ser analisado segundo os numeros de Fibonacci, uma vez determinada a escala de observacao. Defende que as relacoes entre picos e vales do grafico da flutuacao de bolsa tendem a seguir razoes numericas aproximadas das razoes de dois numeros consecutivos da sequencia de Fibonacci.Teorias mais recentes, defendem que e possivel encontrar relacoes de ouro entre os pontos de pico e os de vale, como no grafico abaixo:Se tomarmos o valor entre o inicio do ciclo e o primeiro pico, e o compararmos com o valor entre este pico e o pico maximo, encontraremos tambem o numero de ouro. O ciclo, naturalmente, pode estar invertido, e os momentos de pico podem se tornar momentos de vale, e vice-versa. GeneralizacoesUma generalizacao da sequencia de Fibonacci sao as sequencias de Lucas. Um tipo pode ser definido por:U(0) = 0U(1) = 1U(n+2) = PU(n+1) QU(n)onde a sequencia normal de Fibonacci e o