A) Defina A=\left(\begin{array}{ll}1 & 1 \\\\ 1 & 0\end{array}\right). Demonstre que A^{n}=\left(\begin{array}{cc}F_{n+1} & F_{n} \\\ F_{n} & F_{n-1}\end{array}\right), para todo n \geq 2, onde \left(F_{n}\right) é a sequência de Fibonacci \left(F_{1}=F_{2}=1 \mathrm{e}\right. F_{n+2}=F_{n+1}+F_{n}, para todo n \geq 1 ).
B) Usando que A^{m+n}=A^{m} A^{n} para demonstrar que F_{m+n}=F_{m+1} F_{n} +\mathrm{F}_{\mathrm{m}} \mathrm{F}_{\mathrm{n}-1}, para todos \mathrm{m}, \mathrm{n} \geq 1.

Passo 1

O enunciado dá a matriz
A=\begin{pmatrix}1 & 1 \\[4pt] 1 & 0\end{pmatrix}
e a sequência de Fibonacci \left(F_n\right) definida por \,F_1=F_2=1 e \,F_{n+2}=F_{n+1}+F_n para todo n\ge 1.
São duas coisas a demonstrar:
A) Mostrar que, para todo n\ge 2,
A^{n}=\begin{pmatrix}F_{n+1} & F_{n} \\[4pt] F_{n} & F_{n-1}\end{pmatrix}.
B) Usando a propriedade A^{m+n}=A^{m}A^{n}, provar que, para todos m,n\ge 1,
F_{m+n}=F_{m+1}F_{n}+F_{m}F_{n-1}.
Listei o que foi dado (a matriz A e a definição de F_n) e o que é pedido (as duas identidades acima). A partir daqui vou provar passo a passo, sem pular etapas.]

Passo 2

Antes de começar a prova, vamos fixar umas noções básicas que usaremos e explicá-las com calma:
  1. Definição de potência de matriz: para uma matriz quadrada A, define-se A^1=A e, para k\ge 1, A^{k+1}=A^k A. Ou seja, multiplicamos A por ela mesma k vezes.
  2. Multiplicação de matrizes 2×2: se
X=\begin{pmatrix}x_{11} & x_{12}\\[4pt] x_{21} & x_{22}\end{pmatrix},\qquad Y=\begin{pmatrix}y_{11} & y_{12}\\[4pt] y_{21} & y_{22}\end{pmatrix},
então
XY=\begin{pmatrix} x_{11}y_{11}+x_{12}y_{21} & x_{11}y_{12}+x_{12}y_{22}\\[4pt] x_{21}y_{11}+x_{22}y_{21} & x_{21}y_{12}+x_{22}y_{22} \end{pmatrix}.
Vou usar esta fórmula repetidas vezes, então quando multiplicarmos matrizes vou calcular cada entrada com essa soma de produtos.
  1. Princípio da indução matemática: para provar que uma propriedade P(n) vale para todo n a partir de algum inteiro mínimo, mostramos (i) que P vale para o caso base (por exemplo n=2) e (ii) que se P(k) vale então P(k+1) vale. Isso é suficiente para concluir que P(n) vale para todos n a partir do caso base.
  2. A relação de recorrência dos Fibonacci F_{n+2}=F_{n+1}+F_n será usada para mostrar que as entradas das potências de A “andam” como Fibonacci.
Agora que temos essas ferramentas claras, começo a prova de A por indução.]

Passo 3

Caso base: n=2.
Calculemos A^2 diretamente usando a fórmula de multiplicação de matrizes:
A^2 = A\cdot A = \begin{pmatrix}1 & 1 \\[4pt] 1 & 0\end{pmatrix} \begin{pmatrix}1 & 1 \\[4pt] 1 & 0\end{pmatrix}.
Usando a regra do produto:
  • Entrada (1,1): 1\cdot 1 + 1\cdot 1 = 2.
  • Entrada (1,2): 1\cdot 1 + 1\cdot 0 = 1.
  • Entrada (2,1): 1\cdot 1 + 0\cdot 1 = 1.
  • Entrada (2,2): 1\cdot 1 + 0\cdot 0 = 1\cdot 1 + 0 = 1.
Portanto
A^2=\begin{pmatrix}2 & 1 \\[4pt] 1 & 1\end{pmatrix}.
Agora compare com Fibonacci: \,F_1=1,\;F_2=1,\;F_3=F_2+F_1=2. Assim
\begin{pmatrix}F_{3} & F_{2} \\[4pt] F_{2} & F_{1}\end{pmatrix} = \begin{pmatrix}2 & 1 \\[4pt] 1 & 1\end{pmatrix},
o que coincide com A^2. Logo a propriedade é verdadeira para n=2.]

Passo 4

Hipótese de indução: suponha que para algum k\ge 2 vale
A^{k}=\begin{pmatrix}F_{k+1} & F_{k} \\[4pt] F_{k} & F_{k-1}\end{pmatrix}.
Vou mostrar que então vale a mesma forma para k+1.]

Passo 5

Usando a definição de potência, A^{k+1}=A^{k}A. Substituo a hipótese de indução para A^k e multiplico por A:
A^{k+1} = \begin{pmatrix}F_{k+1} & F_{k} \\[4pt] F_{k} & F_{k-1}\end{pmatrix} \begin{pmatrix}1 & 1 \\[4pt] 1 & 0\end{pmatrix}.
Vou calcular cada entrada do produto aplicando a fórmula de multiplicação de matrizes:
  • Entrada (1,1):
F_{k+1}\cdot 1 + F_{k}\cdot 1 = F_{k+1}+F_k.
Pela relação de Fibonacci, F_{k+1}+F_k = F_{k+2}. Logo a entrada (1,1) é F_{k+2}.
  • Entrada (1,2):
F_{k+1}\cdot 1 + F_{k}\cdot 0 = F_{k+1}.
Então a entrada (1,2) é F_{k+1}.
  • Entrada (2,1):
F_{k}\cdot 1 + F_{k-1}\cdot 1 = F_k + F_{k-1} = F_{k+1}.
Então a entrada (2,1) é F_{k+1}.
  • Entrada (2,2):
F_{k}\cdot 1 + F_{k-1}\cdot 0 = F_k.
Então a entrada (2,2) é F_k.
Portanto
A^{k+1}=\begin{pmatrix}F_{k+2} & F_{k+1} \\[4pt] F_{k+1} & F_{k}\end{pmatrix},
que é exatamente a forma desejada com n=k+1.]

Passo 6

Conclusão por indução: pelo passo base ( n=2) e pelo passo indutivo (se vale para k então vale para k+1), a fórmula
A^{n}=\begin{pmatrix}F_{n+1} & F_{n} \\[4pt] F_{n} & F_{n-1}\end{pmatrix}
é verdadeira para todo n\ge 2. Isso resolve a parte A.]

Passo 7

Agora parte B: usar A^{m+n}=A^{m}A^{n} para obter a identidade entre Fibonacci.
Pela parte A, para m\ge 1 e n\ge 1 (a fórmula vale para m,n\ge 2; mas as expressões abaixo também fazem sentido para m=1 ou n=1 se lembrarmos que F_0 pode ser tomado como 0 consistentemente com a recorrência; contudo usarei m,n\ge 1 como pedido), temos:
A^{m}=\begin{pmatrix}F_{m+1} & F_{m} \\[4pt] F_{m} & F_{m-1}\end{pmatrix}, \qquad A^{n}=\begin{pmatrix}F_{n+1} & F_{n} \\[4pt] F_{n} & F_{n-1}\end{pmatrix}.
Multiplicando A^{m}A^{n} usando a fórmula de multiplicação:
A^{m}A^{n}= \begin{pmatrix} F_{m+1}F_{n+1}+F_{m}F_{n} & F_{m+1}F_{n}+F_{m}F_{n-1}\\[6pt] F_{m}F_{n+1}+F_{m-1}F_{n} & F_{m}F_{n}+F_{m-1}F_{n-1} \end{pmatrix}.
Mas pela propriedade dada A^{m+n}=A^{m}A^{n} e pela parte A a matriz A^{m+n} também pode ser escrita como
A^{m+n}=\begin{pmatrix}F_{m+n+1} & F_{m+n} \\[4pt] F_{m+n} & F_{m+n-1}\end{pmatrix}.
Agora basta comparar a entrada (1,2) (primeira linha, segunda coluna) das duas expressões para obter a identidade desejada:
Da expressão do produto temos que a entrada (1,2) é F_{m+1}F_{n}+F_{m}F_{n-1}. Da expressão de A^{m+n} a entrada (1,2) é F_{m+n}. Igualando-as obtemos
F_{m+n}=F_{m+1}F_{n}+F_{m}F_{n-1},
para todos m,n\ge 1.]

Resposta

A) \displaystyle A^{n}=\begin{pmatrix}F_{n+1} & F_{n} \\[4pt] F_{n} & F_{n-1}\end{pmatrix} para todo n\ge 2.
B) \displaystyle F_{m+n}=F_{m+1}F_{n}+F_{m}F_{n-1} para todos m,n\ge 1.]

Exercícios relacionados