A sequência de \underline{\boldsymbol{F} \boldsymbol{\operatorname { ibon }} \boldsymbol{a} \boldsymbol{c} \boldsymbol{c} \boldsymbol{i}} é uma sequência de inteiros tal que cada termo a partir do terceiro é a soma dos dois termos precedentes, além disso, os dois primeiros termos são iguais a 1, em símbolos temos:
F_{1}=F_{2}=1 \quad \text { e } \quad F_{n}=F_{n-1}+F_{n-2}, \quad \forall n \geq 3
Com isso, prove as seguintes afirmações: F_{1}^{2}+F_{2}^{2}+\ldots+F_{n}^{2}=F_{n} \cdot F_{n+1} para todo n \geq 1.
Passo 1
O enunciado dá a sequência de Fibonacci definida por
As informações relevantes são: a definição recursiva dos termos \,F_n e a identidade que queremos demonstrar para todo n.
Passo 2
Verifiquemos os primeiros casos (base da indução) para ganhar confiança e preparar a prova por indução.
Para n=1:
F_{1}^{2}=1^{2}=1
e
F_{1}\cdot F_{2}=1\cdot 1=1.
Portanto a identidade vale para n=1.
Para n=2:
F_{1}^{2}+F_{2}^{2}=1^{2}+1^{2}=1+1=2
e como F_{3}=F_{2}+F_{1}=1+1=2,
F_{2}\cdot F_{3}=1\cdot 2=2.
Logo a identidade vale também para n=2. Esses casos base mostram que a fórmula começa correta.
Passo 3
Explicando a ideia da prova por indução (passo a passo, sem pressa): a indução matemática funciona assim — mostramos que a proposição é verdadeira para um primeiro valor (já fizemos para n=1), e então mostramos que, se ela é verdadeira para um índice genérico k, então também é verdadeira para k+1. Isso garante que a verdade “se propaga” de 1 para 2, de 2 para 3, e assim por diante, cobrindo todos os inteiros n\ge 1.
Passo 4
Formulemos a hipótese de indução. Suponha que para algum k\ge 1 vale
Isto é a nossa hipótese de indução — estamos assumindo que a identidade é verdadeira até o termo k. Nosso objetivo é provar que então também vale para k+1.
Passo 5
Partimos da soma até k+1. Usamos a hipótese de indução para substituir a soma até k e depois manipulamos algebricamente:
Começando,
F_{1}^{2}+F_{2}^{2}+\cdots+F_{k}^{2}+F_{k+1}^{2}.
Pela hipótese de indução a parte até k é F_{k}\cdot F_{k+1}. Assim a soma inteira é
F_{k}\cdot F_{k+1}+F_{k+1}^{2}.
Agora fatoramos F_{k+1} (aqui usamos a propriedade distributiva da multiplicação sobre a soma, que diz que a b + a c = a(b+c)):
F_{k+1}\bigl(F_{k}+F_{k+1}\bigr).
Mas pela definição de Fibonacci (a recursão) temos
Concluímos a prova por indução: como a identidade vale para n=1 (base) e mostramos que, se vale para um k arbitrário então vale para k+1 (passo indutivo), segue que a identidade é verdadeira para todo n\ge 1.