RESOLVENDO RELAÇÕES DE RECORRÊNCIA

Considere novamente a sequência S definida por
○ S(1) = 2
■ S(n) = 2 * S(n­1) para n ≥ 2
○ Observe o seu comportamento:
■ S(1) = 2 = 21 ■ S(2) = 2*S(2­1) = 2* S(1) = 2* 21 = 22 ■ S(3) = 2*S(3­1) = 2* S(2) = 2* 22 = 23 ■ S(4) = 2*S(4­1) = 2* S(3) = 2* 23 = 24
■
○
○
○
○
○
○
○
○
○
...
Podemos concluir que S(n) = 2n e usar esta equação para calcular S(n) para qualquer valor de n, sem precisar calcular S para valores menores que n.
Uma equação desse tipo é chamada uma Solução de Forma Fechada para uma relação de recorrência sujeita à hipótese básica estabelecida (isto é, pela base de recorrência).
Resolver uma Relação de recorrência é encontrar uma solução de forma fechada para a relação de recorrência.
A relação de recorrência pode ser resolvida usando­se uma abordagem em três etapas:
■ Expandir
■ Supor
■ Verificar
Nesta abordagem a relação de recorrência é usada repetidamente para expandir a expressão para o n­ésimo termo, até que se possa deduzir um padrão geral de comportamento da expreessão. Por último, a suposição deve ser demonstrada por indução matemática.
Exemplo: Expandindo a relação de recorrência da sequência S definida anteriormente:
■ S(n) = 2S(n ­ 1) = 2 [ 2S(n ­ 1)] = 22 S(n ­ 2)
= 22 [ 2S(n ­ 2)] = 23 S(n – 3)
Após k expansões sucessivas:
■ S(n) = 2k S(n – k)
A expansão dos valores de S em termos do valores inferiores de S deve parar quando n ­ k = 1 (porque a base da recorrência é definida para 1), ou seja, quando k = n – 1. Neste ponto teremos:
■ S(n) = 2n­1 S(n – (n – 1)) = (2n/2)*S(1) = (2n/2)*2 = 2n ■ S(n) = 2n é a solução de forma fechada encontrada para a relação de recorrência S(n) = 2S(n ­ 1) Para verificar a solução da forma fechada precisamos agora demonstrar sua validade por indução matemática em n
■ S(n) = 2n ■ BASE: S(1) = 21 = 2
OK
k
■ Hipótese Indutiva: S(k) = 2 ● Queremos mostrar que S(k+1) = 2k+1 ● Da definição de S e usando a hipótese indutiva
○ S(k+1) = 2*S(k + 1 ­ 1) = 2*S(k) = 2*(2k) = 2k+1
○ c.q.d

Exemplo ­ Encontre uma solução de forma fechada para a relação de recorrência sujeita à hipótese básica para a sequência T a seguir:
1. T(1) = 1
2. T(n) = T(n­1) + 3
Expandindo a relação de recorrência
■ T(n) = T(n­1) + 3
= T(n­2) + 3 + 3 = T(n­2) + 2*3
= T(n­3) +3 + 3 + 3 = T(n­3) + 3*3
Após k expansões sucessivas:
○ T(n) = T(n­k) + k*3
A expansão dos valores de T em termos do valores inferiores de T deve parar quando n ­ k = 1 , ou seja, quando k = n – 1. Neste ponto teremos:
○ T(n) = T(1) + (n­1)*3 = 1 + 3n – 3 = 3n – 2
Para verificar a solução da forma fechada precisamos agora demonstrar sua validade por indução matemática em n
○ T(n) = 3n – 2
○ BASE: T(1) = 3*1 – 2 = 3 – 2 = 1
OK
○ Hipótese Indutiva: T(k) = 3k – 2
○ Queremos mostrar que T(k+1) = 3(k+1) – 2 = 3k + 3 – 2 = 3k + 1
○ Da definição de T e usando a hipótese indutiva
■ T(k+1) = T(k+1­1) + 3 = T(k) + 3 = 3k – 2 + 3 = 3k + 1
■ c.q.d
○




TIPOS DE RELAÇÃO DE RECORRÊNCIA
○ Relação de recorrência LINEAR
■ Os valores anteriores que aparecem na definição são apenas de primeira potência
■ S(n) = c*f1(n)S(n­1)+c*f2(n)S(n­2)+ ... + c*fk(n)S(n­k) + g(n)
■ Onde fi e g podem ser expressões envolvendo n
■ Diz­se que a relação de recorrência tem COEFICIENTES CONSTANTES se os fi são todos constantes
■ Diz­se que a relação de recorrência é de PRIMEIRA ORDEM se o n­ésimo termo depende apenas dos termos de ordem n­1
■ Uma recorrência LINEAR de PRIMEIRA ORDEM com COEFICIENTES CONSTANTES tem a forma: ● S(n) = c*S(n­1) + g(n)
(1)
■ Uma relação de recorrência é HOMOGÊNEA se g(n) = 0 para todo n
● S(n) = c*S(n­1)

SOLUÇÃO DE FORMA FECHADA DA EQUAÇÃO (1) ○ S(n) = c*S(n­1) + g(n) é uma relação de recorrência LINEAR, de PRIMEIRA ORDEM, com COEFICIENTES CONSTANTES, sujeita à hipotese básica S(1), que é conhecida.
○
Expandir ­ Supor ­ Verificar
■ S(n) = c.S(n­1) + g(n)
= c.[ c.S(n­2)+g(n­1)]+g(n)
= c2.S(n­2)+c.g(n­1)+g(n)
= c2.[c.S(n­3)+g(n­2)]+c.g(n­1)+g(n)
= c3.S(n­3)+c2.g(n­2)+c.g(n­1)+g(n)
■ Após k expansões
● S(n) = ck.S(n­k)+ck­1.g(n­(k­1)+ ... +c.g(n­1)+g(n)
■ Se a sequência tem valor base igual a 1, então a expansão termina quando n – k = 1, ou k = n – 1. Neste ponto teremos:
■ S(n) = cn­1.S(1)+cn ­2.g(2)+ ... +c.g(n­1)+g(n)
■ S(n) = cn­1.S(1)+cn ­2.g(2)+ ... +c1.g(n­1)+c0.g(n)
n
■
S(n) = cn­1.S(1)+ ∑ cn ­i.g(i)
(2)
i=2
● Solução de forma fechada para a relação de recorrência da equação (1)
■
Prova por indução ● BASE:
1
○
S(1) = c0.S(1)+ ∑ cn­i.g(i) = 1.S(1) + 0 = S(1)
i=2
●
Hipótese indutiva
k
○
S(k) = ck­1.S(1)+ ∑ ck­i.g(i) i=2
○
Queremos provar que
k+1
○
S(k+1) = ck+1­1.S(1)+ ∑ ck+1 ­i.g(i) i=2
k+1
○
S(k+1) = ck.S(1)+ ∑ ck+1 ­i.g(i) i=2
○
Pela relação de recorrência:
■ S(k+1) = c.S(k) + g(k+1)
k
= c[ck­1.S(1)+ ∑ ck ­i.g(i)] + g(k+1) i=2
k
= ck.S(1)+ c.∑ ck ­i.g(i) + g(k+1) i=2
k
= ck.S(1)+ ∑ ck+1­i.g(i) + g(k+1) i=2
k+1
= ck.S(1)+ ∑ ck+1 ­i.g(i) ­ c(k+1) ­(k+1).g(k+1)+ g(k+1) i=2
k+1
= ck.S(1)+ ∑ ck+1 ­i.g(i) ­ c0.g(k+1)+ g(k+1) i=2
k+1
= ck.S(1)+ ∑ ck+1 ­i.g(i) ­ g(k+1)+ g(k+1) i=2
k+1
= ck.S(1)+ ∑ ck+1 ­i.g(i)
i=2

(c.q.d)
EXEMPLO:
1. S(1) = 2
2. S(n) = 2.S(n­1) ○
○
S(n) é uma relação de recorrência:
■ LINEAR – valores anteriores de S que aparecem na definição ocorrem apenas à primeira potência
■ DE PRIMEIRA ORDEM – o n­ésimo termo depende apenas dos termos de ordem n­1
■ COM COEFICIENTES CONSTANTES – fs são constantes (c=2)
■ Em outras palavras, ela ferifica com a equação (1), com c=2 e g(n) = 0 para todo n
Da equação (2)
n
■
■
S(n) = cn­1.S(1)+ ∑ cn ­i.g(i)
i=2
S(n) = 2n­1.2 = 2n
confirmando o resultado obtido anteriormente