Número de Fibonacci

Origem: Wikipédia, a enciclopédia livre.

Na matemática, os Números de Fibonacci são uma seqüência (sucessão, em Portugal) definida como recursiva pela fórmula abaixo:

$F(n)= \left\{ \begin{matrix} 0\,,\qquad\qquad\qquad\quad\,\ \ \,&&\mbox{se }n=0\,;\ \ \\ 1,\qquad\qquad\qquad\qquad\,&&\mbox{se }n=1;\ \ \,\\ F(n-1)+F(n-2)&&\mbox{outros casos.} \end{matrix} \right.$

Na prática: você começa com 0 e 1, e então produz o próximo número de Fibonacci somando os dois anteriores para formar o próximo. Os primeiros Números de Fibonacci (sequência A000045 em On-Line Encyclopedia of Integer Sequences) para n = 0, 1,... são

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946...

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

[editar] Origens

Esta seqüência foi descrita primeiramente por Leonardo de Pisa, também conhecido como Fibonacci (c. 1200), para descrever o crescimento de uma população de coelhos. Os números descrevem o número de casais em uma população de coelhos depois de n meses se for suposto que:

no primeiro mês nasce apenas um casal,
casais amadurecem sexualmente (e reproduzem-se) apenas após o segundo mês de vida,
não há problemas genéticos no cruzamento consangüíneo,
todos os meses, cada casal fértil dá a luz a um novo casal, e
os coelhos nunca morrem.

A fórmula acima se aplica ao problema dos coelhos porque se no mês n existir a coelhos, e no mês n + 1 existir b coelhos, então no mês n + 2 existirá, necessariamente, a + b coelhos. Isto acontece porque é sabido que cada coelho basicamente dá a luz a outro coelho todos os meses (na verdade, cada casal dá a luz a outro casal, mas é a mesma coisa), e isto significa que todos os a coelhos darão a luz a outro número de a coelhos que se tornarão férteis depois de dois meses, que é exatamente o mês n + 2. Então, no mês n + 2, existirá a população do momento n + 1 (que é b) mais a população no momento n (que é a).

O termo seqüência de Fibonacci é também aplicado mais genericamente a qualquer função g onde g(n + 2) = g(n) + g(n + 1). Estas 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 seqüências de Fibonacci formam um espaço vetorial com as funções F(n) e F(n + 1) como base.

Em particular, a seqüência de Fibonacci com F(1) = 1 e F(2) = 3 é conhecida como os números de Lucas. A importância dos números de Lucas L(n) reside no fato deles gerarem a Proporção áurea para as enésimas potências:

$\left( \frac 1 2 \left( 1 + \sqrt{5} \right) \right)^n = \frac 1 2 \left( L(n) + F(n) \sqrt{5} \right)$

Os números de Lucas se relacionam com os de Fibonacci pela fórmula:

L (n) = F (n - 1) + F (n + 1)

[editar] Fórmula explicita

Conforme mencionado por Johannes Kepler, a taxa de crescimento dos números de Fibonacci, que é F(n + 1) /F(n), tende à Proporção áurea, denominada φ. Esta é a raiz positiva da equação de segundo grau x² − x − 1 = 0, então φ² = φ + 1. Se multiplicarmos ambos os lados por φⁿ, teremos φⁿ⁺² = φⁿ⁺¹ + φⁿ, então a função φⁿ é 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 φⁿ e (1 − φ)ⁿ formam outra base para o espaço.

Ajustando os coeficientes para obter os valores iniciais adequados F(0) = 0 e F(1) = 1, temos

$F\left(n\right) = {\phi^n \over \sqrt{5}} - {(1-\phi)^n \over \sqrt{5}}$

Este resultado também pode ser derivado utilizando-se a técnica de gerar funções, ou a técnica de resolver relações recursivas lineares.

Quando n tende a infinito, o segundo termo tende a zero, e os números de Fibonacci tendem à exponencial φⁿ/√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.

[editar] Calculando números de Fibonacci

Na prática não é possível calcular os números de Fibonacci usando potências da proporção áurea, a não ser para valores pequenos 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.

A implementação direta da definição recursiva da sequência de Fibonacci também 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). 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.

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:

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F\left(n+1\right) & F \left(n\right) \\ F\left(n\right) & F \left(n-1\right) \end{bmatrix}$

onde a potência de n é calculada elevando-se a matriz ao quadrado repetidas vezes.

[editar] 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 seqüencia 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 (1.609) é próximo de φ (1.618) (obviamente ele só é útil para aproximações bem grosseiras: além do factor de conversão ser diferente de φ, a série converge para φ).

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 seqüência de Fibonacci na construção do seu modulor, um sistema de proporções baseadas no corpo humano e aplicadas ao projeto de arquitetura.

[editar] Generalizações

Uma generalização da seqüência de Fibonacci são as Seqüências de Lucas. Um tipo pode ser definido assim:

U(0) = 0

U(1) = 1

U(n+2) = PU(n+1) − QU(n)

onde a seqüência normal de Fibonacci é o caso especial de P = 1 e Q = -1. Outro tipo de seqüência de Lucas começa com V(0) = 2, V(1) = P. Tais seqüências têm aplicações na Teoria de Números e na prova que um dado número é primo (primalidade).

Os polinômios de Fibonacci são outra generalização dos números de Fibonacci.

[editar] Identidades

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

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

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

Podemos provar essas identidades usando diferentes métodos. Mas, entretanto, nós queremos demonstrar uma elegante prova para cada um de seus usos aqui. Particularmente, F(n) podem ser interpretados como o número de formas de adicionar 1's e 2's até n − 1, convencionando-se que F(0) = 0, significando que nenhuma soma irá adicionar até -1, e que F(1) = 1, significando que a soma 0 será "adicionada" até 0. Aqui a ordem dos numeros importa. Por exemplo, 1 + 2 e 2 + 1 são consideradas duas diferentes somas e são contadas duas vezes.

Prova da primeira identidade .

Sem perda de generalidade, podemos assumir n ≥ 1. Então F(n + 1) conta o número de formas de somar 1's e 2's até n.

Quando o primeiro summand é 1, há F(n) formas de completar a contagem para n − 1; e o primeiro summand é 2, há F(n − 1) formas de completar a contagem para n − 2. Portanto, no total, há F(n) + F(n − 1) formas de completar a contagem para n. $\Box$

Prova da segunda identidade.

Contamos o número de formas de somar 1's e 2's até n + 1 such that at least one of the summands is 2.

Como antes, há F(n + 2) formas de somar 1's e 2's até n + 1 quando n ≥ 0. Já que há apenas uma soma n + 1 que não usa nenhum 2, namely 1 + … + 1 (n + 1 termos), subtraímos 1 de F(n + 2).

Equivalentemente, podemos considerar a primeira ocorrência de 2 como um adendo.

Se, em uma soma, o primeiro adendo é 2, então há F(n) formas de completar a contagem para n − 1. Se o segundo adendo é 2 mas o primeiro é 1, então há F(n − 1) formas de completar a contagem para n − 2. Proceed in this fashion.

Finalmente consideramos (n + 1)-th como adendo. Se é 2 mas todos os adendos n anteriores são 1's, então há F(0) formas de completar a contagem para 0. Se uma soma contém 2 como um adendo, a primeira ocorrência de tal adendo tomar lugar lugar entre a primeira e a (n + 1)-th posição. Portanto F(n) + F(n − 1) + … + F(0) dá a contagem desejada. $\Box$

Prova da terceira identidade.

Essa identidade pode ser estabelecida em duas fases. Primeiro, contamos o número de formas de somar 1's e 2's até -1, 0, …, ou n + 1 tal que pelo menos um dos adendos seja 2.

Pela nossa segunda igualdade, há F(n + 2) − 1 formas de somar até n + 1; F(n + 1) − 1 formas de somar até n; …; e, finalmente, F(2) − 1 formas de somar até 1.

Como F(1) − 1 = F(0) = 0 , podemos adicionar todos as somas n + 1 e aplicar a segunda igualdade novamente para obter: [F(n + 2) − 1] + [F(n + 1) − 1] + … + [F(2) − 1]

= [F(n + 2) − 1] + [F(n + 1) − 1] + … + [F(2) − 1] + [F(1) − 1] + F(0)

= F(n + 2) + [F(n + 1) + … + F(1) + F(0)] − (n + 2)

= F(n + 2) + F(n + 3) − (n + 2).

Por outro lado , observamos a partir da segunda igualdadee que existem

F(0) + F(1) + … + F(n − 1) + F(n) meios somando com n + 1;
F(0) + F(1) + … + F(n − 1) meios somando com n;

……

F(0) meio somando com -1.

Somando todas as somas n + 1 , vemos que há

(n + 1) F(0) + n F(1) + … + F(n) formas de somar até -1, 0, …, ou n + 1.

Já que os dois métodos de contagem se referem ao mesmo numero , temos : (n + 1) F(0) + n F(1) + … + F(n) = F(n + 2) + F(n + 3) − (n + 2)

Finalmente, completamos a prova subtraindo a igualdade acima de n + 1 vezes a segunda igualdade. $\Box$

[editar] Número Tribonacci

Um número Tribonacci assemelha-se a um número de Fibonacci, mas em vez de começarmos com dois termos pré-definidos, a sequência é iniciada com três termos pré-determinados, e cada termo posterior é a soma dos três termos precedentes. Os primeiros números de uma pequena sequência Tribonacci são:

1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, etc.

OEIS: A000073

[editar] Número Tetranacci

Um número Tetranacci assemelha-se a um número Tribonacci, com a diferença que são quatro termos pré-determinados, e cada termo seguinte é a soma dos quatro termos precedentes. Os primeiros números Tetranacci de uma pequena série seriam

1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, etc.

OEIS number: A000078

Números Pentanacci, Hexanacci e Heptanacci podem ser computados, mas não têm interessado muito os pesquisadores.

[editar] Repfigits

Um repfigit ou número de Keith é um número inteiro, tal que os seus dígitos, ao começar uma seqüência de Fibonacci, alcançam posteriormente o referido número. Um exemplo é 47, porque a seqüência de Fibonacci que começa com 4 e 7 (4, 7, 11, 18, 29, 47) alcança o 47. Um repfigit pode ser uma seqüência de Tribonacci se houver três dígitos no número, e de Tetranacci se o número tiver quatro dígitos, etc.