thumb|350px|direita|Yupana (em quíchua, "instrumento de contagem"): calculadora usada pelos incas, possivelmente baseada nos números de Fibonacci.Andean Calculators
Na matemática, a sucessão de Fibonacci (ou sequência de Fibonacci), é uma sequência de números inteiros, começando normalmente por 0 e 1, na qual cada termo subsequente corresponde à soma dos dois anteriores. A sequência recebeu o nome do matemático italiano Leonardo de Pisa ou Leonardo Fibonacci, mais conhecido por apenas Fibonacci, que descreveu, no ano de 1202, o crescimento de uma população de coelhos, a partir desta. Esta sequência já era, no entanto, conhecida na antiguidade.
Os números de Fibonacci são, portanto, os números que compõem a seguinte sequência (A000045 na OEIS): 0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, ... .Pela convenção moderna a sequência inicial começa por F0 = 0. No livro Liber Abaci (veja Seção Origens) esta começava com F1 = 1, omitindo-se o zero inicial.Lista com os 2000 primeiros números da sequência de Fibonacci. <https://oeis.org/A000045/b000045.txt>. Consultado em 09 de maio de 2016
Em termos matemáticos, a sequência é definida recursivamente pela fórmula abaixo, sendo o primeiro termo F1= 1:
e valores iniciais Ou, de acordo com a nota: Pode ser representada também pela fórmula matemática:
A sequência de Fibonacci tem aplicações na análise de mercados financeiros, na ciência da computação e na teoria dos jogos. Também aparece em configurações biológicas, como, por exemplo, na disposição dos galhos das árvores ou das folhas em uma haste, no arranjo do cone da alcachofra, do abacaxi, ou no desenrolar da samambaia.
Origens No ocidente, a sequência de Fibonacci apareceu pela primeira vez no livro Liber Abaci (1202) de Leonardo Fibonacci, Capítulo II.12, pp. 404–405. embora ela já tivesse sido descrita por gregos e indianos. Fibonacci considerou o crescimento de uma população idealizada (não realista biologicamente) de coelhos. Os números descrevem o número de casais na população de coelhos depois de n meses se for suposto que: miniaturadaimagem|340px|Ilustração representativa da série de Fibonacci, demonstrando o crescimento populacional de coelhos (carregando ovos de páscoa) no primeiro mês nasce apenas 1 casal; casais amadurecem de forma sexual (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.
Mas genericamente, chama-se sequência de Fibonacci qualquer função g tal que g(n + 2) = g(n) + g(n + 1). Essas 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 F(2) = 3 é conhecida como a sequência de Lucas. A importância dos números de Lucas L(n) reside no fato deles gerarem a Proporção áurea para as n-ésimas potências:
Os números de Lucas se relacionam com os de Fibonacci pela fórmulas:
e
Observando-se que logo e que pois é a solução de e substituindo isso em obtemos a fórmula apenas em termos da raiz positiva:
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: none|Uma grade preenchida com quadrados cujos lados são números de Fibonacci, formando sucessivamente retângulos cada vez maiores e tendentes à razão áurea
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, ...
Representações alternativas Para analisar a sequência de Fibonacci (e, em geral, quaisquer sequências) é conveniente obter outras maneiras de representá-la matematicamente.
Observação: os números da sequência também podem ser calculados por:
Observe que não é possível reduzir essa expressão à fórmula de recorrência apesar de ambas fornecerem o mesmo resultado na sequência de Fibonacci.
Função geradora Uma função geradora para uma sequência qualquer é a função
ou seja, uma série potências formais em que cada coeficiente é um elemento da sequência. Os números de Fibonacci possuem a seguinte função geradora
Quando se expande esta função em potências de os coeficientes são justamente os termos da sequência de Fibonacci:
Fórmula explícita Conforme mencionado por Johannes Kepler, a taxa de crescimento dos números de Fibonacci, que é tende à Proporção áurea, denotada por Em outras palavras, (De um modo mais geral, ) 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, tem-se a fórmula de Binet:
Este resultado também pode ser derivado utilizando-se a técnica de funções geradoras, ou a técnica de resolver relações de recorrência.
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.
Fórmula de Binet e o Binômio de Newton Se expandirmos a Fórmula de Binet usando o Binômio de Newton, é possível também escrevê-la em termos racionais, ou seja, nessa forma: a) Se for ímpar:
b) Se for par:
Ou ainda, de modo equivalente: onde representa a parte inteira de (n-1)/2.
Função inversa da fórmula de Binet Para resolver o problema inverso, ou seja, qual a posição que um dado número de Fibonacci ocupa na sequência, existe a função inversa da fórmula de Binet:Mathematics - "How can I find an inverse to the Binet formula?". <http://math.stackexchange.com/questions/374758/how-can-i-find-an-inverse-to-the-binet-formula>. Consultado em 09 de maio de 2016.
1) O número dado é um número de Fibonacci se for um número inteiro e positivo. Como ainda não sabemos o valor de (temos apenas o número que desejamos calcular: o suposto ), há que se testar inicialmente as duas possibilidades. Se for ímpar, então será inteiro, e se for par, então será inteiro.
2) A posição que esse número ocupa na sequência é calculada por:
Onde representa a parte inteira de
Exemplos:
1) Dado o número 1597, verifique se ele pertence à sequência de Fibonacci e, em caso afirmativo, determine a sua posição na sequência. Verificamos que é inteiro, o que indica que ele pertence à sequência e neste caso é ímpar.
Aplicando-se a função inversa da fórmula de Binet para
Lembrando que elevado a qualquer número ímpar sempre resulta Logo:
o que significa que 1597 é o 17° número da sequência de Fibonacci. De fato:
2) Verifique se o número pertence ou não à sequência de Fibonacci.
Neste caso, nem e nem são números inteiros, o que indica que não é um número de Fibonacci.
De fato, e
Forma matricial 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:
em que a potência de n é calculada através do produto matricial 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 sobre o máximo divisor comum do wikilivro de Teoria de números.
thumb|Representação da Série de Fibonacci na Molle Antonelliana em Turim, Itália
Tipos de algoritmos Há diversos algoritmos (métodos) para calcular o -ésimo elemento da sequência de Fibonacci, sendo que os mais comuns empregam um das seguintes abordagens: Recursiva Iterativa Dividir para conquistar
A seguir é apresentado um exemplo de cada um destes tipos de algoritmos em pseudocódigo.
Abordagem recursiva A própria definição da sequência de Fibonacci pode ser tomada como base para implementar um algoritmo recursivo que gera os termos da sequência, como é mostrado a seguir:
função se então retorne caso contrário retorne
Apesar de simples, essa estratégia 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). Uma análise cuidadosa mostra que a complexidade computacional do algoritmo é 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.
Uma outra alternativa é fazer uso da fórmula apresentada na seção anterior, que envolve potências da proporção áurea. No entanto, isso pode não ser muito conveniente para valores grandes 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.
Abordagem iterativa Com o uso de um algoritmo iterativo como o que é mostrado a seguir, é possível obter a sequência um pouco mais eficientemente:
função
para de até faça
retorne
Neste caso, a complexidade computacional do algoritmo é
Abordagem dividir para conquistar O algoritmo abaixo é bem mais eficiente e baseia-se na representação matricial da sequência de Fibonacci. Sua complexidade computacional é
função se então retorne
enquanto faça se é impar então
retorne
Algoritmo em C O algoritmo abaixo é um exemplo de como escrever um código simples em C para encontrar a sequência de Fibonacci.#include <stdio.h> main(){ int N, num, numA, numB, i; printf("Digite quantos termos devem aparecer.\n"); scanf("%d", &N); numA = 1; numB = 0; i = 0; while(i < N){ printf("%d, ", numA); num = numA + numB; numB = numA; numA = num; i++;
Aplicações Os números de Fibonacci são importantes para a análise em tempo real do algoritmo euclidiano, para determinar o máximo divisor comum de dois números inteiros.
Matiyasevich mostrou que os números de Fibonacci podem ser definidos por uma Equação diofantina, o que o levou à solução original do Décimo Problema de Hilbert.
Os números de Fibonacci aparecem na fórmula das diagonais de um triângulo de Pascal (veja coeficiente binomial).
Um uso interessante da sequência de Fibonacci é na conversão de milhas para quilômetros. Por exemplo, para saber aproximadamente a quantos quilômetros 5 milhas correspondem, pega-se o número de Fibonacci correspondendo ao número de milhas (5) e olha-se para o número seguinte (8). 5 milhas são aproximadamente 8 quilômetros. Esse método funciona porque, por coincidência, o fator de conversão entre milhas e quilômetros () é próximo de φ () (obviamente ele só é útil para aproximações bem grosseiras: além do factor de conversão ser diferente de φ, a série converge para φ).
thumb|Exemplo de sons Fibonacci
Em música os números de Fibonacci são utilizados para a afinação, tal como nas artes visuais, determinar proporções entre elementos formais. Um exemplo é a Música para Cordas, Percussão e Celesta de Béla Bartók.
Le Corbusier usou a sequência de Fibonacci na construção do seu modulor, um sistema de proporções baseadas no corpo humano e aplicadas ao projeto de arquitetura.