Considere a recorrência definida por
, se
, onde
são constantes.
Se
e
, mostre, por indução em
, que:
.
Passo 1
O enunciado dá a recorrência de primeira ordem não homogênea
onde
são constantes e
.
O objetivo é provar por indução que, para todo ,
O objetivo é provar por indução que, para todo
Passo 2
(Base da indução,
).
Substituindo na fórmula proposta, obtemos
Substituindo
que coincide com a condição inicial
. Logo, vale para
.
Passo 3
(Hipótese de indução).
Suponha que, para algum , valha
Suponha que, para algum
Passo 4
(Passo de indução).
Usando a recorrência e a hipótese, temos
Usando a recorrência
Observe que
Logo
que é exatamente a fórmula desejada para
.
Resposta
Para todo
,