Demonstre, usando o princípio da indução finita.
.
Passo 1
Queremos provar por indução finita que
O método de indução finita consiste em verificar um caso base e depois mostrar que, se a propriedade vale para um
, ela vale também para
.
Passo 2
Caso base (
): checamos
Como
é verdadeiro, o caso base está estabelecido.
Passo 3
Hipótese indutiva: suponha que, para algum
, valha
Essa é a nossa hipótese de indução.
Passo 4
Passo indutivo: devemos mostrar
Começamos calculando
Pela hipótese indutiva
, temos
E, como
para todo
, pela transitividade de
concluímos
Logo a propriedade vale para
.
Resposta
Pelo princípio da indução finita, segue que
para todo
.