Considere a relação definida recursivamente por
, e
Prove, usando indução em
, que:
, para
.
Passo 1
O enunciado define duas sequências
e
por
e pede para provar, por indução em
, que
O método será Indução Matemática.
Passo 2
(Caso base.) Para
calculamos primeiro
Então
logo a propriedade vale para
.
Passo 3
(Passo indutivo.) Suponha que para algum
valha a hipótese
Queremos mostrar que
Usando a definição recursiva,
Expandindo,
Assim
Pela hipótese indutiva
, segue
Isso completa o passo indutivo.
Resposta
Concluímos por indução que, para todo
, vale