Um problema de Fibonacci

Derivando a Matemática

Fórmula fechada com diagonalização

Uma breve introdução

Em 1202, um matemático italiano conhecido como Fibonacci propôs o seguinte problema:

Um coelho macho e uma fêmea nascem no início do ano. Assumindo que:

Depois de dois meses de idade, o casal de coelhos produz um par misto (um macho e uma fêmea), e então outro par misto de coelhos a cada mês.
Não ocorrem mortes durante o ano.

Quantos coelhos teremos no fim do ano?

Considere $ f_n $ o número de pares de coelhos no começo no mês $ n $. Assim, temos que:

$$
\begin{alignat*}{5}
f_0 = 1, \quad && f_1 = 1, \quad && f_2 = 2, \quad && f_3 = 3, \quad && f_4 = 5, \ \dots
\end{alignat*}
$$

para fixar idéias, observe a imagem ao lado.

Assim, podemos observar que $ f_n = f_{n-1} + f_{n-2} $. Isto significa que todos os termos da sequência (a partir de $ n= 2 $), são obtidos pela soma dos dois termos anteriores.

A sequência gerada a partir dessa construção, foi nomeada Sequência de Fibonacci, em homenagem ao matemático Leonardo Fibonacci, também conhecido como Leonardo de Pisa.E os primeiros 20 números da sequência encontram-se na tabela.

Veja que com base na tabela, conseguimos resolver o problema, pois sabemos que o número de casais cresce de acordo com os termos da sequência, onde:

$$ f_n = f_{n-1} + f_{n-2} $$

Então, ao final de um ano (12 meses) teremos: $ f_{12} = 144 $ casais de coelhos.

Contudo, veja que quando queremos calcular o termo $ f_n $ da sequência, onde $ n $ é um número muito grande, esta expressão não é muito viável, visto que com ela deveremos calcular todos os termos anteriores a $ f_n $. O que vamos fazer é encontrar uma fórmula fechada para o termo $ f_n $ da Sequência de Fibonacci.

$$
\begin{array}{|l|l|l|l|}
\hline
n \hphantom{1111} & f_n \hphantom{111} & n \hphantom{111} & f_n \hphantom{1} \\
\hline
0 \hphantom{1111} & 1 \hphantom{111} & 10 \hphantom{111} & 89 \hphantom{1} \\
\hline
1 \hphantom{1111} & 1 \hphantom{111} & 11 \hphantom{111} & 144 \hphantom{1} \\
\hline
2 \hphantom{1111} & 2 \hphantom{111} & 12 \hphantom{111} & 233 \hphantom{1} \\
\hline
3 \hphantom{1111} & 3 \hphantom{111} & 13 \hphantom{111} & 377 \hphantom{1} \\
\hline
4 \hphantom{1111} & 5 \hphantom{111} & 14 \hphantom{111} & 610 \hphantom{1} \\
\hline
5 \hphantom{1111} & 8 \hphantom{111} & 15 \hphantom{111} & 987 \hphantom{1} \\
\hline
6 \hphantom{1111} & 13 \hphantom{111} & 16 \hphantom{111} & 1597 \hphantom{1} \\
\hline
7 \hphantom{1111} & 21 \hphantom{111} & 17 \hphantom{111} & 2584 \hphantom{1} \\
\hline
8 \hphantom{1111} & 34 \hphantom{111} & 18 \hphantom{111} & 4181 \hphantom{1} \\
\hline
9 \hphantom{1111} & 55 \hphantom{111} & 19 \hphantom{111} & 6765 \hphantom{1} \\
\hline
\end{array}
$$

Termo geral da sequência de Fibonacci usando diagonalização de matrizes

Para resolver o problema de encontrar uma fórmula fechada de um termo $f_n$ $ f_n $ da sequência de Fibonacci, iremos relembrar e usar alguns conceitos da Álgebra linear:

Definição: Seja A uma matriz $ n \times n $. O escalar $ \lambda$ é um autovalor de $ A $ quando existe um vetor $ \mathbf{x} $ não nulo tal que $ A \mathbf{x} = \lambda \mathbf{x} $. O vetor $ \mathbf{x} $ é um autovetor de $ A $ associado a $ \lambda$.

Exemplo: Seja $ A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $. Temos que $ \begin{bmatrix} 1 &1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 1 + \sqrt{5} \\ 2 \end{bmatrix} = \frac{1 + \sqrt{5}}{2} \begin{bmatrix} 1 + \sqrt{5} \\ 2 \end{bmatrix} $.

Neste caso, $ \begin{bmatrix} 1 + \sqrt{5} \\ 2 \end{bmatrix} $ é um autovetor de $ A $, correspondente ao autovalor $ \frac{ 1 + \sqrt{5} } {2} $.

Para descobrir os autovalores e autovetores de uma matriz quadrada usamos o seguinte teorema.

Teorema: Dada uma matriz $ A $ de dimensões $ n \times n $:

os autovalores de $ A $ são as soluções da equação $ Det( \lambda I \ – \ A ) = 0 $. Onde $ I $ é a matriz identidade de ordem $ n $
os autovetores de $ A $ associados a $ \lambda $ são as soluções não nulas do sistema homogêneo $ ( \lambda I \ – \ A ) \mathbf{x} = 0 $.

Demonstração

Seja $ A $ a matriz identidade $ n \times n $. Temos que:

$$ \begin{alignat*}{5} A \mathbf{x} = \lambda \mathbf{x} \quad && \Rightarrow \quad && \lambda I \mathbf{x} = A \mathbf{x} \quad && \Rightarrow \quad && (\lambda I \ – \ A) \mathbf{x} = 0 \end{alignat*} $$

E este é um sistema homogêneo de equações, e portanto possui soluções não nulas se e somente se, a matriz dos coeficientes $ (\lambda I \ – \ A ) $ não for inversível, isto é, se e somente se seu determinante for zero. Logo, se $ Det( \lambda I \ – \ A ) = 0 $ temos que $ \lambda $ é um autovalor de $ A $. E as soluções de $ ( \lambda I \ – \ A) \mathbf{x} = 0 $ são os autovetores de $ A $ associados a $ \lambda $.

Exemplo: Aplicando o teorema na matriz $ A $ anterior temos:

$$ \begin{vmatrix} \lambda -1 &-1 \\ -1&\lambda \end{vmatrix} = 0 \Rightarrow \lambda^2 – \lambda + 1 = 0 $$

Resolvendo a equação, obtemos os autovalores da matriz $ \lambda_1 = \frac{ 1 + \sqrt{5 }} {2} $ e $ \lambda_2 = \frac{ 1 – \sqrt{5 }} {2} $.

E para encontrar os autovetores de $ A $? Usamos o seguinte resultado:

Definição: Definimos o autoespaço $ E_{ \lambda } $ correspondente ao autovalor $ \lambda $ como sendo o conjunto de todos os autovetores de $ \lambda $, juntamente com o vetor nulo. Em outras palavras, $ E_{ \lambda } $ é a solução do sistema $ ( \lambda I \ – \ A) \mathbf{x} = 0 $

Exemplo: Novamente retornando ao primeiro exemplo, para encontrar os autovetores da matriz $ A $ correspondentes ao autovalor $ \lambda_1 = \frac{ 1 + \sqrt{5 }} {2} $, devemos resolver o sistema:

$$ (\lambda I \ – \ A) \mathbf{x} = 0 \quad \Rightarrow \quad \begin{bmatrix} \frac{ 1 + \sqrt{5} } {2} – 1 & – 1 \\ -1 & \frac{ 1 + \sqrt{5} } {2} \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $$

Fazendo $ L_2 \hspace{0.5em} \leftarrow \hspace{0.5em} L_2 \ – \ \left( \frac{-\sqrt{5}-1}{2} \right) \cdot L_1 $ obtemos que:

$$ \begin{bmatrix} \frac{\sqrt{5} – 1} {2} & -1 \\ 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} \quad \Rightarrow \quad \mathbf{x} = t \begin{bmatrix} \frac{1 + \sqrt{5} } {2} \\[1mm] 1 \end{bmatrix} ,\ t \in \mathbb{R} $$

Logo, uma solução geral é $ \mathbf{x} = t \begin{bmatrix} \frac{1 + \sqrt{5} } {2} \\[1mm] 1 \end{bmatrix} ,\ t \in \mathbb{R} $. Em particular, $ \mathbf{x_1} = \begin{bmatrix} \frac{1 + \sqrt{5} } {2} \\[1mm] 1 \end{bmatrix} $ é uma base para o autoespaço $ E_{\lambda_1} $.

Do mesmo modo, mostramos que $ \mathbf{x_2} = \begin{bmatrix} \frac{1 – \sqrt{5} } {2} \\[1mm] 1 \end{bmatrix} $ é uma base do autoespaço $ E_{\lambda_2} $. Em particular, temos que $ dim(E_{\lambda_1}) + dim(E_{\lambda_2}) = 2 $.

Definição: Uma matriz quadrada é chamada diagonal quando todas as suas entradas são nulas, exceto, talvez, as entradas da diagonal principal.

Definição: Uma matriz quadrada $ A $ de ordem $ n $ é dita diagonalizável quando é semelhante a uma matriz diagonal, isto é, $ A $ é diagonalizável quando existe matriz $ P $ inversível de mesma ordem tal que $ P^{-1} A P $ é uma matriz diagonal.

O próximo teorema nos fornece um algoritmo para a diagonalização de matrizes:

Teorema: Seja $ A $ uma matriz $ n \times n $, $ D $ uma matriz diagonal qualquer, e $ \lambda_1 , \dots , \lambda_k $ os autovalores distintos (reais) de $ A $. Temos o seguinte:

$A$ é diagonalizável se, e somente se, $ dim( E_{\lambda_1} ) + \cdots + dim( E_{\lambda_k} ) = n $
Se $ A $ é diagonalizável com $ P^{-1} A P = D $, as colunas de $ P $ são vetores de base para os autoespaços de $ A $ e as entradas diagonais de $ D $ são os autovalores correspondentes.

Exemplo: Vamos novamente considerar a matriz $ A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $. Como vimos acima que $ dim( E_{\lambda_1} ) + dim( E_{\lambda_2} ) = 2 $, segue do teorema que $A$ é diagonalizável. Agora, seja:
$$ P = \begin{bmatrix} \frac{1 + \sqrt{5} } {2} & \frac{1 – \sqrt{5} } {2}\\[1mm] 1 & 1 \end{bmatrix} $$

, a matriz cujas colunas são formadas pelos autovetores de $A$. Calculando a matriz inversa de $P$ obtemos:

$$ P^{-1} = \begin{bmatrix} \frac{1}{\sqrt{5} } & \frac{-(1 – \sqrt{5}) } {2\sqrt{5} }\\[2mm] \frac{-1}{\sqrt{5}} & \frac{(1 + \sqrt{5}) } {2\sqrt{5}} \end{bmatrix} $$

Portanto, como no teorema, temos que a decomposição de $A$ é dada por:

$$ A=\begin{bmatrix} \frac{1 + \sqrt{5} } {2} & \frac{1 – \sqrt{5} } {2}\\[1.5mm] 1 & 1 \end{bmatrix} \begin{bmatrix} \frac{(1 + \sqrt{5}) } {2} & 0\\ 0& \frac{(1 – \sqrt{5}) } {2} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{5}} & \frac{-(1 – \sqrt{5}) }{2\sqrt{5}}\\[2mm] \frac{-1} {\sqrt{5} } & \frac{(1 + \sqrt{5}) } {2\sqrt{5} } \end{bmatrix} $$

Obtendo a fórmula fechada

Agora podemos aplicar todos os resultados anteriores para encontrar uma formula fechada que nos dê $ f_n $. Vimos que o termo $ f_n $ da sequência pode ser obtido fazendo-se $ f_n = f_{n-1} + f_{n-2} $, porém, para $ n $ grande, esta expressão não é muito conveniente. O que podemos fazer aqui é transformar o problema em um problema mais simples, usando matrizes. A ideia é calcular o vetor $$ V_n=\begin{bmatrix} f_{n+1}\\ f_n \end{bmatrix}$$ para cada $ n \ge 0 $ em vez de $ f_n $ em si. A relação $ f_n = f_{n-1} + f_{n-2} $ nos dá: $$ V_{n+1}=\begin{bmatrix} f_{n+2}\\ f_{n+1} \end{bmatrix} = \begin{bmatrix} f_{n+1}+f_n\\ f_{n+1} \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \cdot\begin{bmatrix} f_{n+1}\\ f_{n} \end{bmatrix} $$ onde $ A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $, como em todos os exemplos anteriores. Usando a relação $ V_n = A V_{n-1} $, $ n \ge 0 $ que obtivemos acima, temos: $$ V_n = A V_{n-1} = A^2 V_{n-2} = A^3 V_{n-3} = \cdots = A^n V_{0} $$ mas veja que $ A^n = P D^n P^{-1} $, onde $$ P=\begin{bmatrix} \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2}\\[1mm] 1 & 1 \end{bmatrix}, \ D=\begin{bmatrix} \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2}\\[1mm] 1 & 1 \end{bmatrix} $$ Logo, temos que $$ V_n = A^n V_0 = P D^n P^{-1 }V_0 = \begin{bmatrix} \vphantom{ \left( \frac{\sqrt{}}{\sqrt{}} \right)^n } \frac{1 + \sqrt{5} } {2} & \frac{1 – \sqrt{5} } {2} \\[1mm] \vphantom{ \left( \frac{\sqrt{}}{\sqrt{}} \right)^n } 1 & 1 \end{bmatrix} \begin{bmatrix} \left( \frac{1 + \sqrt{5} } {2} \right)^n & 0 \\[1mm] 0 & \left( \frac{1-\sqrt{5} } {2} \right)^n \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{5}} & \frac{-(1-\sqrt{5}) } {2\sqrt{5}}\\[2mm] \frac{-1}{\sqrt{5}} & \frac{1+\sqrt{5} } {2\sqrt{5}} \end{bmatrix} \begin{bmatrix} \vphantom{ \left( \frac{\sqrt{}}{\sqrt{}} \right)^n } 1 \\ \vphantom{ \left( \frac{\sqrt{}}{\sqrt{}} \right)^n } 1 \end{bmatrix} $$ Realizando as multiplicações e olhando para a primeira componente do resultado, obteremos que: : $$ f_{n+1} = \frac{1} {\sqrt{5} } \begin{bmatrix} \left( \frac{1 + \sqrt{5} } {2} \right)^{n+1} – \left( \frac{1 – \sqrt{5} } {2} \right)^{n+1} \\ \end{bmatrix} $$ como queríamos.

$\square$

Usando essa fórmula, podemos calcular qualquer termo da sequência de Fibonacci.

Fontes

KHOURY, J. Application to a probleme of Fibonacci. Disponível em: <http://aix1.uottawa.ca/~jkhoury/fibonacci.htm>. Acesso em: 13 fev. 2020.

LARSON, Ron. Elementos de álgebra linear. 8 ed. São Paulo: Cengage, 2017.