Monografia- MA148
Professor: Fernando Torres
Sequência de Fibonacci
Alunos:
Luiz Pedro Corradini ra: 136746
Carlos Eduardo Dalefi ra: 151044
Renam Ribeiro Chaves ra: 137436
Orlando da Cunha Vasconcellos Neto ra: 092532
Índice
O que são os números de Fibonacci.............................03
Origem.............................................................................03
Representações alternativas..........................................05
Tipos de algoritmos........................................................06
Generalizações................................................................07
Aplicações.......................................................................08
Gráficos...........................................................................08
Onde encontramos o número de Fibonacci?...............09
Curiosidades sobre Fibonacci.......................................10
O que são os números de Fibonacci
A sucessão de Fibonacci, ou sequência de Fibonacci é uma sequência de números
naturais, na qual os primeiros dois termos são 0 e 1, e cada termo subseqüente
corresponde à soma dos dois precedentes.
A sequência tem o nome do matemático pisano do século XIII Leonardo de Pisa,
conhecido como Leonardo Fibonacci, e os termos da sequência são chamados números
de Fibonacci. Os números de Fibonacci são, portanto, os números que compõem a
seguinte sequência de números inteiros (sequência A000045 na OEIS):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Em termos matemáticos, a sequência é definida recursivamente pela fórmula abaixo,
sendo os dois primeiros termos F0= 0 e F1= 1.
Em seu livro de 1202, intitulado Liber Abaci, Fibonacci introduziu a sequência na
matemática da Europa Ocidental, embora ela já tivesse sido descrita anteriormente por
matemáticos indianos. No Liber Abaci, a sequência começa com F1 = 1, omitindo-se o
zero inicial, e alguns ainda escrevem a sequência dessa forma.
A sequência de Fibonacci tem aplicações na análise de mercados financeiros, na ciência
da computação e na teoria dos jogos. Também aparece em configurações biológicas,
como, por exemplo, na disposição dos galhos das árvores ou das folhas em uma haste,
no arranjo do cone da alcachofra, do abacaxi, ou no desenrolar da samambaia.
Origem
No ocidente, a sequência de Fibonacci apareceu pela primeira vez no livro Liber Abaci
(1202) de Leonardo de Pisa, conhecido como Fibonacci, embora ela já tivesse sido
descrita por matemáticos indianos. Fibonacci considerou o crescimento de uma
população idealizada (não realista biologicamente) de coelhos. Os números descrevem o
número de casais na 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 consanguíneo,
todos os meses, cada casal fértil dá a luz a um novo casal, e
os coelhos nunca morrem.
Mas genericamente, chama-se sequência de Fibonacci qualquer função g onde g(n + 2) =
g(n) + g(n + 1). Essas 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 sequências de Fibonacci formam um espaço vetorial
com as funções F(n) e F(n + 1) como base.
Em particular, a sequê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 n-ésimas potências:
Os números de Lucas se relacionam com os de Fibonacci pela fórmula:
Com esta fórmula podemos montar a sequência de Fibonacci e descobrir, por exemplo,
quantos coelhos foram gerados no sexto mês, basta aplicar a fórmula descrita acima até
chegar ao ponto inicial de 1 e 1, como mostra a figura abaixo:
Ou seja, no sexto mês foram gerados 8 coelhos.





F(6) = (F(6) - 1) + (F(6) - 2) = 5 e 4 → 8 ( Soma do Resultado de F(5) e F(4) )
F(5) = (F(5) - 1) + (F(5) - 2) = 4 e 3 → 5 ( Soma do Resultado de F(4) e F(3) )
F(4) = (F(4) - 1) + (F(4) - 2) = 3 e 2 → 3 ( Soma do Resultado de F(3) e F(2) )
F(3) = (F(3) - 1) + (F(3) - 2) = 2 e 1 → 2
F(2) = (F(2) - 1) + (F(2) - 2) = 1 e 0 → 1
E a primeira posição sendo 1.
Note que a sequência de Fibonacci esta no resultado de cada posição: 1, 1, 2, 3, 5, 8, ...
Representações alternativas
Função geradora
Uma função geradora para uma sequência qualquer
é a função
Ou seja, uma série potências formais em que cada coeficiente é um elemento da
sequência. Os números de Fibonacci possuem a seguinte função geradora
Quando se expande esta função em potências de , os coeficientes são justamente os
termos da sequência de Fibonacci:
Fórmula explícita
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 φn, teremos φn+2 = φn+1 + φn, então a função φn é 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 φn e (1 − φ)n formam outra base para o
espaço.
Ajustando os coeficientes para obter os valores iniciais adequados F(0) = 0 e F(1) = 1,
tem-se a fórmula de Binet:
Este resultado também pode ser derivado utilizando-se a técnica de funções geradoras,
ou a técnica de resolver relações de recorrência.
Quando n tende a infinito, o segundo termo tende a zero, e os números de Fibonacci
tendem à exponencial φn/√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.
Forma matricial
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:
Em que a potência de n é calculada elevando-se a matriz ao quadrado repetidas vezes.
Tipos de algoritmos
Há diversos algoritmos (métodos) para calcular o -ésimo elemento da sequência de
Fibonacci, sendo que os mais comuns empregam um das seguintes abordagens:



Recursiva
Iterativa
Dividir para conquistar
A seguir é apresentado um exemplo de cada um destes tipos de algoritmos.
Abordagem recursiva
A própria definição da sequência de Fibonacci pode ser tomada como base para
implementar um algoritmo recursivo que gera os termos da sequência, como é mostrado
a seguir: função
se
então
retorne
caso contrário
retorne
Apesar de simples, essa estratégia não é recomendável porque os mesmos valores são
calculados muitas vezes (a não ser que a programação guarde automaticamente os
valores calculados nas chamadas anteriores da mesma função com o mesmo
argumento). Uma análise cuidadosa mostra que a complexidade computacional do
algoritmo é
. 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.
Abordagem iterativa
Com o uso desse algoritmo é possível obter a sequência um pouco mais eficientemente:
função
para
desde
até
faça
retorne
Neste caso, a complexidade computacional do algoritmo é
.
Abordagem dividir para conquistar
O algoritmo abaixo é bem mais eficiente e baseia-se na representação da sequência de
Fibonacci. Sua complexidade computacional é
.
função
se
retorne
então
enquanto
se é par então
faça
retorne
Generalizações
Uma generalização da sequência de Fibonacci são as sequências de Lucas. Um tipo que
pode ser definido por:
U(0) = 0
U(1) = 1
U(n+2) = PU(n+1) − QU(n)
Onde a sequência normal de Fibonacci é o caso especial de P = 1 e Q = -1. Outro tipo
de sequência de Lucas começa com V(0) = 2, V(1) = P. Tais sequências têm aplicações
na Teoria de Números e na prova que um dado número é primo.
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.
Os números de Fibonacci aparecem na fórmula das diagonais de um triângulo de Pascal.
Um uso interessante da sequência 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 φ).
Gráficos
Uma vez determinada a escala de observação, as relações entre picos e vales de um
gráfico da flutuação de bolsa tendem a seguir razões numéricas aproximadas das razões
de dois números consecutivos da sequência de Fibonacci.
Teorias mais recentes, defendem que é possível encontrar relações “de ouro” entre os
pontos de pico e os de vale, como no gráfico abaixo:
Se tomarmos o valor entre o início do ciclo e o primeiro pico, e o compararmos com o
valor entre este pico e o pico máximo, encontraremos também o número de ouro. O
ciclo, naturalmente, pode estar invertido, e os momentos de pico podem se tornar
momentos de queda, e vice-versa.
Onde encontramos o número de Fibonacci?
Natureza
A sequência de Fibonacci está ligada à natureza. Estes números são facilmente
encontrados no arranjo de folhas do ramo de uma planta, em copas das árvores ou até
mesmo no número de pétalas das flores.
As sementes das flores, frutos e, de forma particularmente interessante, as pinhas,
trazem no seu escopo natural esta sequência. Como esta proporção trata-se de uma
sucessão numérica, é possível perceber, em vários traços notáveis, a manifestação desta
em muitos aspectos da natureza de maneira estética e funcional. Tal linha de análise é,
muitas vezes, utilizada como base explicativa para a teoria criacionista denominada
Design Inteligente.
A espiral
Na espiral formada pela folha de uma bromélia, pode ser percebida a sequência de
Fibonacci, através da composição de quadrados com arestas de medidas proporcionais
aos elementos da sequência, por exemplo: 1, 1, 2, 3, 5, 8, 13… , tendentes à razão áurea.
Este mesmo tipo de espiral também pode ser percebida na concha do Nautilus marinho.
Pintura e Arte
Muitos artistas usaram a proporção Áurea em seus trabalhos. Da Vinci a chamava:
Divina Proporção e a usou em muitos de seus trabalhos. Na Mona Lisa observa-se a
proporção Áurea em várias situações. Por exemplo, ao construir um retângulo em torno
de seu rosto, este possui a proporção do retângulo Áureo. Podemos também subdividir
este retângulo usando a linha dos olhos para traçar uma reta horizontal e ter de novo a
proporção Áurea. Podemos continuar a explorar tal proporção em várias outras partes
do corpo. Artistas têm usado a razão de ouro (medida de Ouro) em trabalhos de pintura
e arte. Os trabalhos de Seurat e Mondrian mostram estas relações matemáticas.
Curiosidades sobre Fibonacci
Nasceu na Itália na cidade de Pisa no ano de 1170 e morreu na mesma cidade no ano de
1250, era conhecido também como Leonardo de Pisa, Leonardo Pisano ou
ainda Leonardo Bigollo.
Foi considerado um dos melhores matemáticos da idade média, sendo que foi o
primeiro de tantos outros do período a ter esse título.
Além de ser conhecido pela sua sequência, foi Fibonacci que introduziu os números
arábicos na Europa.
Escreveu diversos livros, entre eles:

Liber Abaci (1202)

Practica Geometriae (1220),

Epistola ad magistrum Theodorum

Flos super solutionibus quorundam questionum ad numerosum vel ad geometriam vel
ad utrumque pertinentium (1225),

Liber quadratorum (1225),).

Di minor guisa (ano não computado)