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 então

retorne

enquanto faça se é par então

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)