Questão 2 (2 pts) - Resolva as seguintes relações de recorrência:
Passo 1
O enunciado dá a recorrência
O que se pede é resolver essa relação de recorrência, ou seja, encontrar uma expressão fechada para
válida (supondo que
permite dividir por
repetidas vezes). Informações relevantes que o enunciado deu:
- A recorrência usa
, logo é natural assumir que é potência de (caso contrário a fórmula precisa de ajuste por piso/ceiling). - O termo não homogêneo é
. - A condição inicial é
.
Passo 2
Primeiro passo técnico: substituir
por uma potência de
. Defina
com
. Isso facilita porque dividir
por
corresponde a diminuir
em
.
Defina a sequência dependente de
:
Agora reescrevemos a recorrência em termos de
. Substituindo
em
obtemos:
Como
, a recorrência fica
Passo 3
Temos agora uma recorrência linear não-homogênea de ordem 1:
Para resolver, procedemos pelo método clássico: encontrar a solução geral da homogênea e uma solução particular da não-homogênea.
A equação homogênea associada é
cuja solução é da forma
onde
é constante arbitrária (porque
é raiz característica).
Passo 4
Agora precisamos de uma solução particular
para
Observação: o termo do lado direito é
, que é solução da homogênea (ressonância). Nesses casos normalmente multiplicamos pela potência de
. Tentamos uma solução particular da forma
onde
é uma constante a determinar.
Vamos calcular o lado esquerdo com essa hipótese:
Note que
, então
Queremos isso igual a
, logo
Portanto uma solução particular é
Passo 5
A solução geral da recorrência é soma da homogênea com a particular:
Use a condição inicial
para determinar
. Substituindo
:
Assim
e
Passo 6
Volte para a variável
. Lembre que
, então
e
. Substituindo:
Passo 7
Conferência rápida (sanity check): pela árvore de recorrência ou pelo Teorema Mestre temos
,
,
. O termo adicional é
, igual ao caso crítico, então a solução assintótica é
. A expressão obtida
é consistente com isso (exatamente
).