Calculadora de Fibonacci

F(1) = 1, F(2) = 1, F(n) = F(n − 1) + F(n − 2) ⇒ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 … ; a razão entre termos consecutivos tende a φ = (1 + √5) / 2 = 1,6180339887…

F(1) = F(2) = 1

Os dois valores iniciais, e a escolha que a página torna explícita. Contar a partir de 1 significa que F(1) e F(2) são ambos 1 e que F(10) é 55. A outra convenção comum fixa F(0) = 0 e F(1) = 1, o que desloca todos os índices em uma posição, de modo que F(5) é 5 em vez de 8. Nenhuma das duas está errada, mas elas discordam sobre cada índice

F(n) = F(n − 1) + F(n − 2)

A recorrência, que é a definição inteira. Cada termo é a soma dos dois anteriores: 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8. Avançar a partir de dois valores iniciais é o motivo de a página produzir mil termos com a mesma facilidade que dez — não há fórmula para resolver, só uma adição repetida

n

Quantos termos você quer, de 2 a 78. O limite inferior é 2 e não 1 porque a saída da razão precisa de um termo e do anterior, então um único termo não teria por que ser dividido; a página recusa a entrada em vez de imprimir uma razão em branco. O limite superior é o ponto em que os termos deixam de ser exatos na aritmética comum de ponto flutuante

F(78) = 8.944.394.323.791.464

O último termo que esta página alcança, e a razão de ela parar aí. F(79) é 14.472.334.024.676.221, que passa do maior número inteiro que um double guarda exatamente — 9.007.199.254.740.991 —, então daquele ponto em diante os algarismos impressos seriam uma aproximação, e não a sequência. A página recusa 79 em vez de imprimir um termo quase certo

F(n) / F(n − 1)

A saída da razão. Ela não é a razão áurea e a página não afirma que seja: 1,6667 é o que se obtém no quinto termo e está longe de 1,618. O que ela é é uma estimativa que melhora rápido — o vigésimo termo já está certo até a sétima casa decimal, que é uma casa a menos do que a precisão impressa pela página

φ = 1.6180339887…

A razão áurea, o número para o qual essas razões convergem. É a solução positiva de x² = x + 1, que é a mesma recorrência escrita como equação — isso não é coincidência, é a razão de as razões de Fibonacci caírem nela. Repare que a estimativa impressa chega no máximo a 1,61803399: a página mostra oito casas decimais, e o valor verdadeiro continua depois delas

Conferir um termo é o uso simples: um enigma pede o décimo número de Fibonacci, ou uma sequência num livro didático vai além do que você quer somar à mão, e a página dá o valor e a série de termos que leva até ele. A saída da razão atende a uma pergunta diferente, que é de onde vem a razão áurea. Ver 1, 2, 1,5, 1,6667, 1,6, 1,625 e 1,615 se acomodando em direção a 1,618 é um caminho muito mais curto para entender a conexão do que ler uma demonstração, e a tabela de referência desta página está montada exatamente para essa leitura. Um terceiro uso é na programação e nos cursos, onde a recorrência é o primeiro exemplo padrão de recursão, e a sequência é o exemplo padrão de uma definição recursiva que sai muito mais barata de forma iterativa — o laço desta página é a versão iterativa, e é por isso que 78 termos não custam nada. Os números também aparecem em problemas de estimativa em que o crescimento se compõe sobre si mesmo: o número de maneiras de ladrilhar uma faixa com quadrados e dominós, o número de caminhos para subir uma escada dando um ou dois degraus por vez, e as contagens de ramificação de uma planta que se divide a cada estação seguem todos a mesma recorrência. Quando a pergunta é sobre a razão e não sobre a sequência, a Calculadora da razão áurea trata esse número como um número por direito próprio, com as suas propriedades; quando é sobre o padrão de crescimento, a Calculadora de crescimento exponencial cobre a versão suave daquilo que estes termos aproximam em degraus.

1. Os primeiros dez termos: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

   1. Comece com 1 e 1, os dois valores iniciais que esta página usa
   2. 1 + 1 = 2, depois 1 + 2 = 3, depois 2 + 3 = 5, depois 3 + 5 = 8
   3. Continue somando: 5 + 8 = 13, 8 + 13 = 21, 13 + 21 = 34, 21 + 34 = 55
   4. Dez termos, então o décimo é 55; a razão dos dois últimos é 55 ÷ 34 = 1,61764706

   A entrada padrão. Repare que o décimo termo é 55 e que a razão de 55 por 34 é 1,61764706 — perto da razão áurea, mas ainda visivelmente fora dela já na terceira casa decimal. É isso que faz a sequência valer a pena acompanhar em vez de apenas consultar: a convergência é rápida, mas não é instantânea, e dez termos ainda não bastam para as oito casas impressas chegarem a 1,61803399.

2. A menor série possível: dois termos

   1. Dois termos é o menor pedido que esta página aceita
   2. A sequência é só os dois valores iniciais: 1 e 1
   3. O segundo termo é 1, então a saída do enésimo termo é 1
   4. A razão é 1 ÷ 1 = 1 — o mais longe que esta página chega da razão áurea

   O limite inferior, e a razão de ele ser 2 e não 1. A saída da razão precisa de dois termos para existir; com um único termo não haveria por que dividir, então a página recusa 1 em vez de imprimir um espaço em branco ou um zero. A razão igual a 1 é também o ponto de partida de toda a convergência: cada razão posterior é um passo a partir dela, e o percurso de 1 até 1,618 é o que a tabela abaixo apresenta termo a termo.

3. Onde a razão se acomoda: vinte termos

   1. Continue a recorrência a partir do décimo termo: 34 + 55 = 89, 55 + 89 = 144, e assim por diante
   2. O vigésimo termo é 6.765, e o décimo nono é 4.181
   3. 6.765 ÷ 4.181 = 1,61803396317…
   4. Arredondado para as oito casas que a página imprime, isso dá 1,61803396

   Vinte termos bastam. A razão áurea verdadeira começa em 1,6180339887, e a estimativa aqui concorda com ela até a sétima casa decimal — a divergência está agora na oitava, que é a última impressa. Compare com o caso de dez termos, em que o erro já aparecia na terceira casa. É esse o ponto que a página existe para mostrar: a recorrência não tem nada a ver com a razão áurea na sua definição, e ainda assim a produz, rápido e a partir de nada além de adição.

O número de termos precisa ser um número inteiro de 2 a 78. O 1 é recusado porque a saída da razão precisa de dois termos para existir, e o 79 é recusado porque os termos deixam de ser exatos ali: F(78) é 8.944.394.323.791.464, o último número de Fibonacci que cabe exatamente em um valor de dupla precisão, e F(79) passa do teto de 9.007.199.254.740.991. A página recusa o pedido em vez de devolver um termo aproximado, já que um número quase certo impresso com dezesseis algarismos é idêntico, para quem lê, a um número correto. A contagem começa em 1 e esta página usa F(1) = F(2) = 1. A outra convenção difundida fixa F(0) = 0 e F(1) = 1, o que desloca todos os índices em uma posição — sob aquela convenção o quinto termo é 5, e aqui é 8. As duas convenções são usadas em livros e em programas, então se você comparar esta página com outra fonte e os números estiverem deslocados em uma posição, é essa a razão, e não um erro. A saída da razão é uma estimativa e é impressa com oito casas decimais; ela nunca é exatamente a razão áurea para nenhum número finito de termos, embora no septuagésimo oitavo o valor impresso e a razão áurea tenham os mesmos oito algarismos. Os termos em si são impressos como uma lista separada por vírgulas, sem nenhum separador de milhar, então o décimo termo sai como 55 e o septuagésimo oitavo sai como uma sequência corrida de dezesseis algarismos — ler termos longos em voz alta é tarefa para a saída do enésimo termo, e não para a lista. Por fim, a tabela de referência é fixa nos dez primeiros termos e não acompanha o que você digitou; ela está ali para mostrar a razão se acomodando, e não para responder à sua entrada.

A sequência começa em F(0) ou em F(1)?

Esta página começa em F(1), então F(1) = 1, F(2) = 1, F(3) = 2, e o décimo termo é 55. A outra convenção difundida fixa F(0) = 0 e F(1) = 1, o que desloca todos os índices em uma posição — sob ela o quinto termo é 5, enquanto aqui é 8. As duas são usadas em livros e em programas, e nenhuma está errada. Mas se você comparar esta página com outra fonte e os valores ficarem deslocados em uma posição, é por isso; é a maneira mais comum de uma resposta de Fibonacci sair errada.

Por que a razão fica mudando em vez de se acomodar de imediato?

Porque ela é um limite, e não uma identidade. Cada termo é a soma dos dois anteriores, então a razão entre termos consecutivos se move por uma regra própria, e o movimento alterna acima e abaixo do alvo, com cada oscilação menor que a anterior. A tabela desta página mostra isso: 1, 2, 1,5, 1,667, 1,6, 1,625, estreitando depois para 1,615 e 1,619. Dez termos ficam perto, vinte bastam para as oito casas impressas menos a última, e nenhum número finito de termos é exatamente a razão áurea — só cada vez mais perto dela.

O que é a razão áurea, e por que esta sequência a produz?

A razão áurea é 1,6180339887…, a solução positiva de x² = x + 1. Essa equação é a recorrência de Fibonacci escrita de outro jeito — se as razões se acomodam em algum número, esse número tem de satisfazê-la —, e é por isso que a sequência cai ali e que a convergência não é coincidência nem curiosidade. A razão áurea é também o número mais difícil de aproximar por frações, porque a fração contínua dela é só 1s, e é essa propriedade que as plantas exploram ao espaçar folhas e sementes por ela.

Por que só posso pedir 78 termos?

Porque F(79) é maior que o maior número inteiro que um valor de dupla precisão guarda exatamente, que é 9.007.199.254.740.991. F(78) é 8.944.394.323.791.464 e é exato; F(79) é 14.472.334.024.676.221 e seria guardado como algo próximo disso, mas não igual. A página recusa o pedido em vez de imprimir uma aproximação, porque um termo impresso com dezesseis algarismos é indistinguível de um termo correto — não há como ver o erro a partir da saída. O limite de termos é um fato do ponto flutuante, e não da matemática; a sequência em si segue para sempre.

Onde entra o problema dos coelhos?

Fibonacci apresentou a sequência com um enigma: comece com um casal de coelhos, deixe cada casal levar um mês para amadurecer e então produzir um novo casal a cada mês, e conte os casais no início de cada mês. As contagens saem 1, 1, 2, 3, 5, 8 e assim por diante, porque os casais maduros do mês passado continuam todos existindo e os casais novos do mês vêm dos que já estavam maduros um mês antes — o que é a recorrência, chegando por uma direção completamente diferente. Vale saber porque mostra que a sequência não é definida por nenhuma aplicação em particular.

Dá para calcular o enésimo termo sem listar todos os anteriores?

Em princípio sim, e a saída do enésimo termo desta página dá esse número em uma linha própria, mas ele é produzido pelo mesmo laço, e não por uma fórmula atalho. A razão é a exatidão: existe uma forma fechada, a fórmula de Binet, que dá o enésimo número de Fibonacci direto a partir da razão áurea, mas ela envolve números irracionais elevados a uma potência, e na aritmética de ponto flutuante ela se afasta do inteiro verdadeiro conforme n cresce. Somar inteiros é exato onde aquela fórmula não é, então a página soma. Avançar a partir de dois valores iniciais é também o motivo de 78 termos não custarem nada — não há fórmula para resolver, só uma adição repetida 76 vezes.

• Fibonacci Number — the recurrence, the closed form in terms of the golden ratio, and the identity that makes the ratio converge on it — Wolfram MathWorld (United States)
• Golden Ratio — the number 1.6180339887…, its definition as the positive root of x² = x + 1, and why it is the hardest number to approximate with fractions — Wolfram MathWorld (United States)
• Continued Fraction — why the all-ones continued fraction of the golden ratio is exactly what makes the Fibonacci ratios converge on it — Wolfram MathWorld (United States)