domingo, 15 de julho de 2012

Sequência de Fibonacci

Olá gente!


Você já deve ter ouvido falar sobre a sequência de Fibonacci. Caso contrário, não tema, pois esse é o nosso assunto de hoje.
Um pouco de história 

Leonardo de Pisa (1170-1250), apelidado de Fibonacci, foi um importante matemático Italiano. Em 1202 publicou um livro chamado Liber Abacci, com grande parte do conhecimento sobre números e álgebra da época. Este livro foi responsável pela introdução do sistema de numeração indo-arábico na Europa e por mais tarde ajudar no desenvolvimento da álgebra e aritmética no ocidente.

O problema

Em seu livro Liber Abacci, Fibonacci enunciou e resolveu o seguinte problema.

Quantos casais de coelhos teriam ao final de 1 ano se:
1- No primeiro mês nasce 1 casal de coelhos
2- Todo mês, cada casal que pode procriar dá a luz a mais 1 casal
3- 1 casal passa a se reproduzir todo mês apenas após o segundo mês de vida
4- É permitido o relacionamento cosanguineo (apenas um detalhe).
5- Os coelhos não morrem

Resolução:
No 12º mês haverá 144 coelhos (Fibonacci apresentou sua solução com uma tabela).

Porém, podemos resolver observando que no mês n teriam o número de casais do mês anterior somado ao número de casais que nasceram, que equivale ao número de casais que haviam há 2 meses atrás. Assim:

No primeiro mês tem 1 casal
No segundo mês tem 1 casal também (pois é 1+0)
No terceiro mês tem 2 casais
No quarto mês tem 3 casais
No quinto mês tem 5 casais
No sexto mês tem 8 casais
No sétimo mês tem 13 casais
No oitavo mês tem 21 casais
No nono mês tem 34 casais
No décimo mês tem 55 casais
No décimo primeiro mês tem 89 casais
No décimo segundo mês tem 144 casais

Se não estiver muito convencido, faça alguns esquemas para entender.
Esse problema foi responsável por introduzir no Ocidente (pois essa sequência já era conhecida na matemática indiana) a "sequência de Fibonacci" da qual falaremos a seguir.

A sequência de Fibonacci

Essa sequência é definida recursivamente como:
[;F_0= 0;]
[;F_1= 1;]
[;F_n= F_{n-1} + F_{n-2};]

Sendo [;F_n;] os termos dessa sequência que são chamados de números de Fibonacci.

Aqui vão os primeiros termos dessa sequência:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

Fórmula de Binet

Assim como as outras sequências na matemática é comum tentar encontrar uma fórmula
fechada para o n-ésimo termo. Essa fórmula existe para a sequência de Fibonacci e é
conhecida como a fórmula de Binet.
Se [;F_n;] é o n-ésimo termo da sequência de Fibonacci, então:
[;F_n= \frac{1}{\sqrt{5}}\cdot \left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1+\sqrt{5}}{2}\right)^n \right];]

Vamos usar indução forte para demonstrar a veracidade desta fórmula.

Se [;n=0;] então: [;F_0=\frac{1}{\sqrt{5}} \cdot (1-1) = 0 \cdot \frac{1}{\sqrt{5}} =0;]

Se [;n=1;] então: [;F_1= \frac{\sqrt{5}}{\sqrt{5}} =1;]

Logo, a hipótese é verdadeira para [;n = 0;] e [;n=1;]

Pela forma recursiva desta sequencia podemos escrever

[;F_{n+1}=;] [;F_n + F_{n-1};]

Porém, por Hipótese:

[;F_{n+1}=;] [;\frac{1}{\sqrt{5}};][;\cdot;][; \left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left( \frac{1-\sqrt{5}}{2}\right)^n \right];] [;+ \frac{1}{\sqrt{5}}\cdot \left[\left(\frac{1+\sqrt{5}}{2}\right)^{n-1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n-1} \right];]


Ou seja...
[;F_{n+1}=;] [;\frac{1}{\sqrt{5}}\cdot;][;\left(\frac{1+\sqrt{5}}{2}\right)^{n} ;] + [;\frac{1}{\sqrt{5}}\cdot;] [;\left(\frac{1+\sqrt{5}}{2}\right)^{n-1};] [;-;][;\frac{1}{\sqrt{5}}\cdot;] [;\left(\frac{1-\sqrt{5}}{2}\right)^{n};][;+;] [;\frac{1}{\sqrt{5}}\cdot;][;\left(\frac{1-\sqrt{5}}{2}\right)^{n-1};]

Observe que:

[;\left(\frac{1+\sqrt{5}}{2}\right);] e [;\left(\frac{1-\sqrt{5}}{2}\right);] são raizes da equação [;x^2=x+1;]

(clique aqui para ler sobre equação do segundo grau)

Então: [;\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}=;] [;\left(\frac{1+\sqrt{5}}{2}\right)^n;] [;+;] [;\left(\frac{1+\sqrt{5}}{2}\right)^{n-1};]

A propriedade acima segue de maneira analoga para [;\left(\frac{1-\sqrt{5}}{2}\right);]
Com isso: [;F_{n+1};] = [;\frac{1}{\sqrt{5}}\cdot;][;\left(\frac{1+\sqrt{5}}{2}\right)^{n+1};] [;-;] [;\frac{1}{\sqrt{5}}\cdot;][;\left(\frac{1-\sqrt{5}}{2}\right)^{n+1};]

C.Q.D.
Algumas propriedades 

Se [;F_n;] é o n-ésimo termo da sequência de Fibonacci, temos algumas propriedades que podem ser demonstradas por INDUÇÃO.


P.1- [;F_1 + F_2 + \cdots + F_n = F_{n+2} -1;]

Para [;n=1;] temos:

[;1;] [;+ 1 = 3-1;]

logo, a base é verdadeira.

Aplicando para [;P_{(n+1)};] temos: [; F_{n+2}-1+F_{n+1}= F_{n+3}-1 = P_{n+1};]
C.Q.D.

P.2- [;F_{n+1} \cdot F_{n-1} - (F_{n})^2 = (-1)^n;]

Para [;n=1;] temos:
[;1;] [;\cdot 0;] [;- 1 =;] [;-1;]

logo, a base é verdadeira

Como [;F_{n+2}= F_{n+1} + F_n e F_{n+1}= F_n + F_{n-1};] temos:

[;(F_{n+1} + F_n) \cdot F_n;] [;- ;] [;(F_n;] [;+ ;] [;F_{n-1});] [;\cdot F_{n+1} =;]

[;(F_n)^2+ F_n ;] [;\cdot;] [;F_{n+1} - F_{n+1};] [;\cdot F_{n-1} =;] [;(F_n)^2;] [;-F_{n+1};] [;\cdot F_{n-1};]

Por hipótese: [;F_{n+1} \cdot F_{n-1} - (F_{n})^2 = (-1)^n;]

Logo, [;(F_{n})^2;] [;- F_{n+1};] [;\cdot F_{n-1}  =;] [;(-1)^n \cdot(-1) = (-1)^{n+1};]


C.Q.D.

P.3- [;\begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1}\end{pmatrix};]

Caso você não saiba o que é uma matriz, clique AQUI.

Vamos verificar para [;n=1;]

[;\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix};]

Logo, a base da indução é verdadeira.


Supondo que [;\begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1}\end{pmatrix};] então:
[;\begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}^n \cdot \begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}  =;][;\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1}\end{pmatrix} \cdot \begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix} =;][;\begin{pmatrix} F_{n+1} \cdot 1 +F_n \cdot 1  & F_{n+1} \cdot 1 + F_n \cdot 0 \\  F_n \cdot 1 + F_{n-1} \cdot 1 & F_n \cdot 1 + F_{n-1} \cdot 0 \end{pmatrix} =;]
[;\begin{pmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n}\end{pmatrix};]


C.Q.D.

Sequência de Fibonacci no mundo real
Já é demonstrado que a razão [;\frac{F_{n+1}}{F_n};] tende a [;\phi;] conforme n aumenta. Essa razão é conhecida
como a razão dourada e tem muitas aplicações em areas como: Biologia, Arquitetura e Design .
Clique aqui para saber mais sobre
[;\phi;]. Por hoje é só, amanha tem mais, se você gostou do blog não esueça de recomendar aos seus
amigos nas redes sociais e de nos seguir por email (para receber nossas atualizações) ou aqui no blog.

Lembre-se: Para melhorar a qualidade de nossas postagens não se esqueça de avaliar o
post aqui embaixo. É rapidinho!
Até mais!

Nenhum comentário:

Postar um comentário

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.

Related Posts Plugin for WordPress, Blogger...