Sequência de Fibonacci

A sequência de Fibonacci (também chamada de série ou sucessão de Fibonacci) é a lista de números 1, 1, 2, 3, 5, 8, 13, 21, 34, …, na qual cada número é a soma dos dois anteriores. Os seus termos são os números de Fibonacci. Você só precisa dos dois primeiros e da regra “some os dois últimos” para continuá-la até onde quiser.

Ela leva o nome de Leonardo de Pisa, chamado Fibonacci, que a usou em 1202 num problema sobre coelhos. Aqui você aprende a formá-la, vê a tabela dos 50 primeiros números, calcula com a fórmula recursiva e com a de Binet, desenha a espiral, vê como programá-la em Python e JavaScript e confere o que é verdade no que se conta sobre a natureza. Quem foi Leonardo está na biografia de Fibonacci (em alemão), e as sequências em geral em Folgen und Grenzwerte (em alemão).

Como se forma a sequência de Fibonacci

Escreva dois números 1. O terceiro número é a soma deles: 1 + 1 = 2. O quarto é a soma do segundo com o terceiro: 1 + 2 = 3. Depois vêm 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13 e assim sem fim. Essa regra de montagem é a lei de formação da sequência.

Muitos livros começam antes, com F₀ = 0 (0, 1, 1, 2, 3, …). A partir de F₁ as duas versões são iguais.

Sequência, série ou sucessão?

Em matemática, uma sequência (ou sucessão, como se diz em Portugal) é uma lista ordenada de números, e uma série é a soma dos termos de uma sequência. Por isso, rigorosamente, o certo é “sequência de Fibonacci”. No uso cotidiano, “série de Fibonacci” significa o mesmo e todo mundo entende. Também não é uma “progressão” no sentido estrito: numa progressão aritmética a diferença é constante, numa geométrica o quociente é constante, e na de Fibonacci não é constante nem uma coisa nem outra.

Números de Fibonacci: tabela dos 50 primeiros

Os números de Fibonacci até 100 são 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 e 89. O seguinte, 144, já passa de 100. A tabela mostra os 50 primeiros termos, com a posição de cada um (a lista de números de Fibonacci de 1 a 50).

F₁₀₀ tem 21 algarismos: 354.224.848.179.261.915.075. A cada cinco termos o número é multiplicado por aproximadamente 11, então, em média, surge um algarismo novo a cada cinco termos.

O problema dos coelhos do Liber abaci

Na Europa a sequência aparece pela primeira vez no livro de cálculo Liber abaci, que Leonardo escreveu em 1202 (capítulo 12). O problema pergunta, em essência: um homem tem um casal de coelhos num recinto fechado. Quantos casais nascem dele em um ano, se cada casal gera um casal novo por mês e os casais novos começam a ter filhotes a partir do segundo mês de vida?

Supomos que o casal inicial é adulto e que nenhum coelho morre. Um casal recém-nascido é jovem demais no mês seguinte e tem o seu primeiro casal de filhotes um mês depois.

Ao fim de doze meses há 377 casais, contando o casal inicial. Nascem tantos casais quanto havia casais adultos dois meses antes, e por isso o total é a soma dos dois meses anteriores. Depois de t meses há F_t+2 casais: o 377 é F₁₄, e não F₁₂. Com 60 meses seriam F₆₂ = 4.052.739.537.881 casais, mais de quatro trilhões.

Fórmula da sequência de Fibonacci: recursiva e explícita

A fórmula recursiva

Você já a conhece: F_n = F_n−1 + F_n−2 com F₁ = F₂ = 1. A desvantagem é que, para chegar a F₄₀, é preciso calcular antes todos os termos anteriores. Exemplo: F₁₅ = F₁₄ + F₁₃ = 377 + 233 = 610.

A fórmula explícita de Binet

Uma fórmula explícita fornece F_n diretamente a partir de n. Na sequência de Fibonacci ela se chama fórmula de Binet, por Jacques Binet (1843). Abraham de Moivre (1718) e Daniel Bernoulli já a conheciam.

A parcela ψⁿ é minúscula para n grande, porque ψ é menor que 1 em valor absoluto. Por isso F_n é simplesmente o número inteiro mais próximo de φⁿ / √5. Para n = 15: φ¹⁵ / √5 ≈ 609,9997, que arredondado é 610 = F₁₅. Se você esquecer de arredondar, a calculadora mostra, para n = 10, o valor 55,0036 (φ¹⁰ / √5) em vez de 55.

Como se chega à fórmula? (Ensino Médio)

1. Procure sequências da forma qⁿ que cumpram qⁿ = qⁿ⁻¹ + qⁿ⁻². Divida por qⁿ⁻² e sobra q² = q + 1.
2. Essa equação do segundo grau tem as soluções q = (1 ± √5) / 2, isto é, φ e ψ.
3. Qualquer combinação a · φⁿ + b · ψⁿ também cumpre a regra.
4. Ajuste a e b a F₀ = 0 e F₁ = 1: de a + b = 0 e a · φ + b · ψ = 1 resulta a = 1 / √5 e b = −1 / √5.

Como calcular com um programa: Python e JavaScript

Para programar a sequência basta um laço: comece com a = 0 e b = 1 e, repetindo n vezes, troque a, b = b, a + b. No fim, a vale F_n. Em Python:

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print([fib(n) for n in range(1, 11)])

A última linha mostra [1, 1, 2, 3, 5, 8, 13, 21, 34, 55], e fib(100) devolve 354224848179261915075. Em JavaScript, com BigInt para não perder precisão nos números grandes:

function fib(n) {
  let a = 0n, b = 1n;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}
console.log(fib(100)); // 354224848179261915075n

A versão recursiva direta, que chama fib(n-1) + fib(n-2), é muito mais lenta: para F₃₀ faz 2.692.537 chamadas, enquanto o laço dá 30 passos. É um exemplo clássico para ensinar por que vale a pena guardar os resultados já calculados. Se você usar a fórmula de Binet com os decimais habituais de um computador (precisão dupla), o resultado deixa de ser exato a partir de F₇₁, porque o computador arredonda.

Fibonacci e o número de ouro

Divida cada número de Fibonacci pelo anterior. Os quocientes primeiro saltam para cima e para baixo, mas se aproximam cada vez mais de um valor fixo.

Eles oscilam em torno de φ ≈ 1,618034, o número de ouro (também chamado de razão áurea, proporção áurea ou seção áurea). O motivo se vê em uma linha: se q = F_n+1 / F_n tende a um valor fixo, de F_n+1 = F_n + F_n−1 resulta q = 1 + 1 / q, ou seja, q² = q + 1. A sua solução positiva é φ. Johannes Kepler notou essa relação em 1611. O que é verdade e o que é lenda em torno do número de ouro está explicado em Der Goldene Schnitt: was stimmt und was Mythos ist (em alemão).

Propriedades simples dos números de Fibonacci

Um em cada três é par

Ímpar mais ímpar dá par, e ímpar mais par dá ímpar. A sequência começa com ímpar, ímpar, então o padrão é i, i, p, i, i, p, … Por isso F₃, F₆, F₉, … são pares: por exemplo, F₁₂ = 144 e F₃₀ = 832.040.

A soma dos n primeiros termos

Exemplo com n = 10: 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143, e F₁₂ − 1 = 144 − 1 = 143. A razão: da regra segue F_k = F_k+2 − F_k+1. Se você escrever cada termo assim, quase tudo se cancela e sobra F_n+2 − F₂ = F_n+2 − 1.

O máximo divisor comum

Para o máximo divisor comum (mdc) vale mdc(F_m, F_n) = F_{mdc(m, n)}. Exemplo: mdc(12, 18) = 6, então mdc(F₁₂, F₁₈) = F₆ = 8. Conferência: 144 = 8 · 18 e F₁₈ = 2.584 = 8 · 323, e 18 e 323 não têm divisores comuns. Como mdc(n, n + 1) = 1 e F₁ = 1, dois números de Fibonacci consecutivos são sempre primos entre si.

A espiral de Fibonacci

Quadrados de lados 1, 1, 2, 3, 5, 8 e 13 se encaixam sem sobras num retângulo. Cada lado é a soma dos dois anteriores, então o novo quadrado cabe exatamente no lado maior do retângulo anterior.

No papel quadriculado, desenhe primeiro dois quadrados de lado 1 lado a lado. Depois acrescente quadrados de lado 2, 3, 5, 8 e 13, cada um encostado no lado maior do retângulo e girando sempre um quarto de volta. Dentro de cada quadrado trace um quarto de círculo cujo raio é o lado, de modo que os arcos se unam.

Cada arco é cerca de 1,6 vez maior que o anterior. Por isso a figura lembra a espiral áurea, que cresce um fator φ a cada quarto de volta, embora não seja exatamente igual: é uma aproximação feita com arcos de circunferência. O retângulo tem 13 · 21 = 273 quadradinhos, e essa é também a soma das áreas 1 + 1 + 4 + 9 + 25 + 64 + 169. Em geral, F₁² + … + F_n² = F_n · F_n+1.

A sequência de Fibonacci na natureza: o que é verdade e o que não é

O exemplo mais conhecido é o girassol. No miolo, com as sementes, aparecem duas famílias de espirais, umas no sentido horário e outras no anti-horário. Se você as contar, muitas vezes obtém dois números de Fibonacci consecutivos, como 34 e 55 ou 55 e 89. Nas pinhas costumam ser 5 e 8 ou 8 e 13, e nos abacaxis também se contam famílias de espirais com números como 8 e 13.

A causa está no crescimento. As sementes novas se formam no ponto de crescimento, cada uma girada o mesmo ângulo em relação à anterior. Com cerca de 137,5° não há duas sementes uma sobre a outra e a superfície se preenche de maneira uniforme. Esse ângulo áureo é 360° / φ² ≈ 137,508°. Ele se relaciona com a sequência: se você multiplicar 360° por frações F_n / F_n+2, os resultados oscilam em torno dele. 2/5 dá 144°, 3/8 dá 135° e 21/55 dá 137,45°.

Mas a natureza nem sempre segue a regra. Em 2016, Jonathan Swinton, Erinma Ochu e muitos colaboradores contaram 657 girassóis. Dos 768 números de espirais avaliados, 565 eram números de Fibonacci, quase três quartos. Outros 67 tinham uma estrutura derivada da de Fibonacci, como a dos números de Lucas 2, 1, 3, 4, 7, 11, … (a mesma regra com outros valores iniciais). O restante não se encaixava em padrão algum.

Para que serve a sequência de Fibonacci?

• Na matemática: é o exemplo mais simples de sequência recursiva e se liga ao número de ouro, às frações contínuas e à teoria dos números.
• Na computação: serve para ensinar recursão e programação com resultados guardados. Além disso, os “heaps de Fibonacci” (Fibonacci heaps), uma estrutura de dados publicada por Michael Fredman e Robert Tarjan em 1987, devem o nome ao fato de que os números de Fibonacci aparecem na análise da sua velocidade.
• Na biologia: descreve bastante bem como folhas, sementes e escamas se dispõem em muitas plantas, com as exceções vistas acima.
• Na arte e na arquitetura: alguns artistas a usam de propósito. Mario Merz, por exemplo, pôs números da sequência em néon sobre pilhas de jornais em obras como 610 Function of 15. As afirmações de que obras antigas “escondem” a sequência costumam carecer de provas, e o arquiteto Le Corbusier baseou conscientemente no número de ouro o seu sistema de medidas, o Modulor.

Exercícios com soluções

Para praticar com mais sequências e com a lei de formação, em alemão você encontra a Folgenrechner (calculadora de sequências) e as folhas de Zahlenfolgen üben.

Perguntas frequentes

Fontes e leituras recomendadas

• Wikipédia: Sequência de Fibonacci
• MacTutor History of Mathematics: Leonardo Pisano Fibonacci (em inglês)
• Parmanand Singh: The So-called Fibonacci Numbers in Ancient and Medieval India, Historia Mathematica 12 (1985), p. 229–244 (em inglês).
• Jonathan Swinton, Erinma Ochu e outros: Novel Fibonacci and non-Fibonacci structure in the sunflower, Royal Society Open Science 3 (2016) (em inglês)
• Ron Knott: The Fibonacci Numbers and Golden Section in Nature (em inglês)
• MOCA Los Angeles: Mario Merz, 610 Function of 15 (em inglês)