Use indução para demonstrar a identidade de Cassini para Fibonacci:
Identifique o uso de modus ponens na passagem de
para
.
Passo 1
O enunciado pede para provar, por indução, a identidade de Cassini
e também identificar onde e como se usa o modus ponens na passagem de
para
.
Informações dadas (ou necessárias):
- Sequência de Fibonacci definida por
- Queremos provar a propriedade para todo
.
Passo 2
Explicação rápida do método que vou usar (indução simples):
- Princípio da indução matemática: para provar que uma proposição
vale para todo , basta: - Mostrar a base
(às vezes também se necessário). - Mostrar que, para todo
, se é verdadeira então também é verdadeira (o chamado passo indutivo).
- Mostrar a base
- Aqui a proposição
é:
Passo 3
Base da indução (
):
Calcular o membro esquerdo para :
Calcular o membro esquerdo para
O lado direito para
é
. Logo
é verdadeira:
Passo 4
Lema útil (identidade algébrica entre os termos consecutivos):
Vou mostrar que, para todo ,
Vou mostrar que, para todo
Prova do lema (contando cada passo):
Começo somando as duas expressões:
Começo somando as duas expressões:
Usando a recorrência
substituo em
:
Assim a soma vira
Cancelando
e agrupando:
Mas pela recorrência
, o parêntese é zero, logo a soma é zero. Portanto
o que dá exatamente
Esse lema é uma identidade verdadeira para todo
(não depende de hipótese indutiva).
Passo 5
Passo indutivo: assumir
e provar
.
Hipótese indutiva: suponha que para um
vale
Pelo lema do passo anterior temos, com
,
Substituindo na expressão da direita a hipótese indutiva:
Assim mostramos
.
Passo 6
Conclusão por indução:
-
é verdadeira (passo 3). - Para todo
, (passo 5).
Pelo princípio da indução,vale para todo . Ou seja, a identidade de Cassini
é verdadeira para todo
.
Passo 7
Explicando lógica e onde o modus ponens aparece:
- Modus ponens é a regra lógica que diz: se temos as proposições
e , então podemos concluir . - No nosso passo indutivo, podemos tomar:
-
como a hipótese indutiva . -
como a implicação obtida do lema (para o mesmo ): (aqui é um placeholder; o lema afirma que o segundo lado é sempre o negativo do primeiro).
-
- Aplicando modus ponens: da hipótese
(onde ) e da implicação (o lema), concluímos , isto é
Portanto a conclusão
decorre por modus ponens a partir da hipótese indutiva e do lema algébrico.
Resposta
O uso de modus ponens ocorre ao combinar a hipótese indutiva