1. Origem Histórica
A sequência de Fibonacci foi apresentada ao mundo ocidental pelo matemático italiano Leonardo de Pisa, conhecido como Fibonacci, em seu livro Liber Abaci (1202). Fibonacci propôs um problema hipotético sobre reprodução de coelhos, cuja solução gerava a famosa sequência. No entanto, a mesma progressão já havia sido descrita séculos antes por matemáticos indianos ao estudar métricas poéticas sânscritas.
A sequência é definida pela relação de recorrência F(n) = F(n−1) + F(n−2), com os valores iniciais F(0) = 0 e F(1) = 1. Os primeiros termos são: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
2. Definição e Propriedades
Além da recorrência básica, a sequência apresenta diversas propriedades notáveis:
- A soma dos n primeiros termos é igual a F(n+2) − 1.
- O máximo divisor comum de dois Fibonacci é outro Fibonacci: mdc(F(m), F(n)) = F(mdc(m, n)).
- Todo inteiro positivo tem uma representação única como soma de Fibonacci não consecutivos (Teorema de Zeckendorf).
- O quadrado de F(n) difere do produto F(n−1)×F(n+1) por exatamente ±1 (Identidade de Cassini).
"A sequência de Fibonacci é uma das mais elegantes em toda a matemática — simples de definir, mas com consequências surpreendentemente profundas."
3. Proporção Áurea e a Fórmula de Binet
A razão entre termos consecutivos F(n+1)/F(n) converge para a Proporção Áurea φ = (1+√5)/2 ≈ 1.6180339887... À medida que n cresce, a convergência é exponencialmente rápida. Para n = 20, a diferença já é inferior a 10⁻⁸.
A Fórmula de Binet fornece uma expressão fechada para F(n) sem recursão: F(n) = (φⁿ − ψⁿ) / √5, onde ψ = (1−√5)/2 ≈ −0.618. Para n grande, o termo ψⁿ torna-se desprezível e F(n) ≈ φⁿ/√5. No entanto, para precisão exata com inteiros grandes, a iteração com BigInt é preferível.
4. Aplicações em Matemática e Computação
A sequência de Fibonacci aparece em contextos variados:
- Algoritmos: a busca de Fibonacci é uma técnica de busca em arrays ordenados com complexidade O(log n).
- Criptografia: alguns esquemas usam propriedades de Fibonacci para geração de chaves ou provas de conhecimento zero.
- Teoria dos grafos: o número de caminhos em certos grafos segue a progressão de Fibonacci.
- Programação dinâmica: calcular Fibonacci é o exemplo canônico de memoização e programação dinâmica bottom-up.
- Arte e arquitetura: a proporção áurea derivada de Fibonacci é aplicada em composição visual, tipografia e design de interfaces.