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:
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:
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.
Vou usar esta fórmula repetidas vezes, então quando multiplicarmos matrizes vou calcular cada entrada com essa soma de produtos.
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.
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:
é 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: