← Voltar para Números de Fibonacci
Sequência de Fibonacci: definição, propriedades, fórmula de Binet e aplicações
Resumo: Guia aprofundado sobre a sequência de Fibonacci — recorrência, provas importantes (Cassini, somas), fórmula fechada (Binet), matriz de Fibonacci, funções geradoras, algoritmos eficientes e a conexão com a razão áurea (φ). Consulte também o nosso conteúdo sobre Números de Fibonacci e a visão sobre irracionais notáveis (π e φ).
Definição e primeiros termos
A sequência de Fibonacci é definida pela recorrência linear de segunda ordem
F₀ = 0, F₁ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ (n ≥ 2)
Os primeiros termos são:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Uma introdução com exemplos elementares está disponível em Números de Fibonacci.
Breve história
Leonardo de Pisa (Fibonacci) popularizou a sequência no Ocidente no século XIII no livro Liber Abaci, usando-a para modelar o crescimento de uma população de coelhos. As propriedades combinatórias e algébricas estudadas desde então transformaram a sequência em um tema central da matemática discreta.
Propriedades fundamentais (e provas rápidas)
Soma dos termos
Para n≥0:
∑_{k=0}^{n} F_k = F_{n+2} − 1.
Prova: por indução usando a recorrência.
Soma dos quadrados
Para n≥0:
∑_{k=0}^{n} F_k² = F_n · F_{n+1}.
Identidade de Cassini
Para todo n≥1:
F_{n+1}F_{n-1} − F_n² = (−1)^n.
MDC entre termos
Se m,n são inteiros positivos então
gcd(F_m, F_n) = F_{gcd(m,n)}.
Essa propriedade liga a aritmética de índices à aritmética dos próprios termos.
Fórmula de Binet e a conexão com a razão áurea (φ)
A equação característica da recorrência é x² = x + 1. Suas raízes são
φ = (1+√5)/2 ≈ 1,6180339887..., ψ = (1−√5)/2 ≈ −0,6180339887...
A fórmula fechada (Binet) é:
F_n = (φⁿ − ψⁿ) / √5.
Como |ψ|<1, para n grande temos
F_n ≈ φⁿ / √5, portanto F_{n+1}/F_n → φ.
Para aprofundar a leitura sobre a razão áurea e implicações geométricas, consulte Número de ouro (φ) e veja a relação entre Fibonacci e irracionais em Números irracionais notáveis: π e φ.
Forma matricial e cálculo eficiente
A recorrência pode ser escrita em forma de matriz 2×2:
[F_{n+1} F_n]^T = [[1,1],[1,0]] · [F_n F_{n-1}]^T
Logo
[F_n F_{n-1}]^T = [[1,1],[1,0]]^{n-1} · [1 0]^T.
Exponenciação rápida de matrizes permite obter F_n em O(log n) multiplicações (cada multiplicação é 2×2), tornando o método ideal para n muito grandes quando se deseja exatidão com inteiros arbitrariamente grandes.
Algoritmo rápido (exemplo em pseudo-código)
// Exponenciação de matriz 2x2 por potência inteira (log n)
function matPow(M, n):
if n == 0: return I2 // matriz identidade 2x2
if n % 2 == 1: return matMul(M, matPow(M, n-1))
X = matPow(M, n/2)
return matMul(X, X)
// Para Fibonacci:
M = [[1,1],[1,0]]
V = matMul(matPow(M, n-1), [1,0]) // V[0] = F_n
Função geradora
A função geradora ordinária G(x) de {F_n} é
G(x) = ∑_{n≥0} F_n x^n = x / (1 − x − x^2).
Essa expressão permite deduzir identidades por manipulação de séries formais e analisar propriedades assintóticas via decomposição em frações parciais.
Identidades clássicas úteis
- Catalan: F_{n+k} = F_k·F_{n+1} + F_{k-1}·F_n
- d’Ocagne: F_m F_{n+1} − F_{m+1} F_n = (−1)^n F_{m−n}
- Soma dos pares: ∑_{k=0}^{n} F_{2k} = F_{2n+1} − 1
- Quadrados: ∑_{k=0}^{n} F_k² = F_n F_{n+1}
Todas podem ser demonstradas por indução, transformações de geradoras ou exponenciação matricial.
Aplicações práticas e interdisciplinres
Algumas aplicações notáveis:
- Combinatória: contagens de tilings (ladrilhamento de um tabuleiro 1×n com 1×1 e 1×2), caminhos e sequências binárias com restrições.
- Ciência da computação: análise de recorrências, heaps de Fibonacci, algoritmos com complexidade amortizada melhorada.
- Natureza e design: filotaxia (disposição de folhas), padrões em pêras, girassóis e conchas, ligando Fibonacci à razão áurea.
- Criptografia e pseudoaleatoriedade: uso de recorrências lineares como geradores (com cuidados sobre período e segurança).
Exercícios dirigidos (níveis progressivos)
- Prove por indução que ∑_{k=0}^{n} F_k = F_{n+2} − 1.
- Mostre a identidade de Cassini: F_{n+1}F_{n-1} − F_n² = (−1)^n.
- Usando a matriz [[1,1],[1,0]], deduza a fórmula de Binet.
- Implemente três métodos para calcular F_n: (a) recursão ingênua, (b) programação dinâmica, (c) exponenciação de matrizes — compare complexidade e uso de memória.
- Mostre que F_{n+1}/F_n → φ e estude a velocidade de convergência (erro assintótico ~ C·ψ^n).