Considere a sequência definida recursivamente por
. Supondo
:
Conjecture uma fórmula para
e prove-a por indução.
Conjecture uma fórmula para
Passo 1
Beleza, o que o enunciado diz é: temos uma sequência onde cada termo vale três vezes o anterior mais quatro, ou seja
e a gente sabe que
. O conteúdo aqui é de recorrência linear de primeira ordem e prova por indução. Para resolver, vamos precisar de:
- Conjecturar a forma fechada de
(usando uma ideia de “solução homogênea + particular” ou desenrolando a recorrência). - Mostrar que essa forma fechada funciona por indução.
Passo 2
Primeiro, vamos chutar (conjecturar) como deve ser
. A técnica mais comum é dividir em duas partes:
- A parte homogênea (
), cuja solução geral é . - Uma parte particular constante, digamos
, que satisfaz .
Então, para achar
, resolvemos:
Isso indica que a solução “total” deve ser da forma
Agora usamos a condição inicial
:
Logo nossa conjectura é
Passo 3
Agora a gente prova por indução que, de fato,
satisfaz a recorrência e a condição inicial.
Base
:
que bate com o dado
.
Hipótese de indução: suponha que para algum
valha
Passo indutivo: precisamos mostrar que então
Usando a definição da recorrência:
Perfeito: a forma que a gente conjecturou satisfaz a relação recursiva. Assim, por indução, vale para todo
.