Recorrência

Matemática Discreta. Recorrência

1. Recorrência

2. Sumário
•Definições Recorrentes
‣Seqüências, conjuntos e operações
•Resolução de Relações de Recorrência

3. Definições Recorrentes
•Uma definição recorrente é uma definição
onde o item sendo definido aparece como
parte da definição.
‣definir algo em termos de si mesmo
•Exemplo: definição recorrente de fatorial

4. Partes de uma
Definição Recorrente
•Base (ou condição básica)
‣casos elementares definidos explicitamente
•Recorrência (ou passo indutivo)
‣demais casos definidos em função dos casos
elementares

5. •Recorrência é uma conceito importante
que pode ser usado para definir:
‣seqüências
‣conjuntos
‣operações
‣algoritmos

6. Seqüências
•Uma seqüência é uma lista ordenada de
elementos
•Exemplo:
‣S = 2, 4, 8, 16, 32, ...
‣S(1) = 2, S(4) = 16

7. Seqüências Definidas
por Recorrência
•Uma seqüência é definida por recorrência
nomeando-se, explicitamente, o primeiro
elemento na seqüência e depois definindo-
se os demais elementos em termos dos
anteriores
•Exemplo (S = 2, 4, 8, 16, 32, ...)
‣S(1) = 2
‣S(n) = 2 * S(n-1), para n ≥ 2

8. Exercício
•Escreve os cinco primeiros valores da
seqüência T definida a seguir
‣T(1) = 1
‣T(n) = T(n-1) + 3

9. Seqüência de Fibonacci
•É uma seqüência de números definida por
recorrência como a seguir:
‣F(1) = 1
‣F(2) = 1
‣F(n) = F(n-1) + F(n-2), para n ≥ 3
•Escreva os 8 primeiros termos da
seqüência de Fibonacci.

10. Conjuntos
•Um conjunto é uma coleção de objetos
‣não há nenhuma ordem imposta à coleção
•Conjuntos podem ser definidos por
relações de recorrência.
‣Base: objetos elementares do conjunto
‣Recorrência: regra para composição de novos
objetos do conjunto

11. Exemplo
•Definição recorrente do conjunto das
fórmulas proposicionais bem formuladas
(FBF)
‣Base: uma proposição é uma FBF
‣Recorrência: se P e Q são FBFs então P ∧ Q, P ∨
Q, P → Q, P′, e P <— Q também são FBFs

12. Operações Definidas
por Recorrência
•Certas operações podem ser definidas de
forma recorrente
•Exemplo: definição recorrente da
exponenciação a
n
‣a
0
= 1
‣a
n
= a * a
n-1
, para n ≥ 1

13. Definições Recorrentes
Seqüência
Pelo menos o primeiro valor é definido
explicitamente; os demais valores são
definidos em termos dos anteriores.
Conjunto
Pelo menos um elemento do conjunto é
definido explicitamente; os demais
elementos são construídos a partir de
elementos que pertencem ao conjunto.
Operação
Um caso trivial (elementar) é definido
explicitamente; demais casos são calculados
a partir de casos menores.

14. Exercícios
•Escreve os cinco primeiros valores da
seqüência M a seguir:
‣M(1) = 2
‣M(2) = 2
‣M(n) = 2*M(n-1) + M(n-2)
•Considerando a série de Fibonacci, prove
que F(n+1) + F(n-2) = 2F(n), para n≥3

15. Considere a seqüência S definida por recorrência:
S(1) = 2
S(n) = 2*S(n-1)
Existe uma equação na qual podemos substituir o
valor de n e calcular diretamente o valor de S(n)
sem ter que calcular os valores anteriores?

16. Considere a seqüência S definida por recorrência:
S(1) = 2
S(n) = 2*S(n-1)
Existe uma equação na qual podemos substituir o
valor de n e calcular diretamente o valor de S(n)
sem ter que calcular os valores anteriores?
S(n) = 2
n

17. Resolvendo Relações
de Recorrência
•Resolver uma relação de recorrência
significa encontrar para ela uma solução em
forma fechada.
•Uma solução em forma fechada para uma
relação de recorrência sujeita a uma
condição básica é uma equação na qual
podemos substituir um valor para calcular
diretamente o elemento que queremos.

18. Estratégias para Resolução
de Recorrências
•Método “expandir, conjecturar e verificar”
•Solução geral
‣no caso de uma relação de recorrência linear de
primeira ordem.

19. “Expandir, conjecturar e
verificar”
•Consiste em usar repetidamente a relação
de recorrência para expandir a expressão
do n-ésimo termo até que seja possível
perceber uma equação para a solução em
forma fechada.
•É preciso verificar a equação encontrada
‣em geral, a verificação pode ser feita por
indução

20. Exemplo
•Considere a condição básica e a relação de
recorrência para a seqüência S a seguir:
‣S(1) = 2
‣S(n) = 2 * S(n-1)
•Encontre a solução em forma fechada para
a relação de recorrência.

21. Passo 1: Expandir
S(n) = 2 * S(n-1)

22. Passo 1: Expandir
S(n) = 2 * S(n-1)
= 2 * 2 * S(n-2)

23. Passo 1: Expandir
S(n) = 2 * S(n-1)
= 2 * 2 * S(n-2)
= 2 * 2 * 2 * S(n-3)

24. Passo 1: Expandir
S(n) = 2 * S(n-1)
= 2 * 2 * S(n-2)
= 2 * 2 * 2 * S(n-3)
= 2 * 2 * 2 * 2 * S(n-4)

25. Passo 2: Conjecturar
S(n) = 2 * S(n-1)
= 2 * 2 * S(n-2)
= 2 * 2 * 2 * S(n-3)
= 2 * 2 * 2 * 2 * S(n-4)
Após k, expansões

26. Passo 2: Conjecturar
S(n) = 2 * S(n-1)
= 2 * 2 * S(n-2)
= 2 * 2 * 2 * S(n-3)
= 2 * 2 * 2 * 2 * S(n-4)
...
= 2
k
* S(n-k)
Após k, expansões

27. S(n) = 2
k
* S(n-k)
Podemos continuar com a expansão
indefinidamente ou existe um limite para k?

28. S(n) = 2
k
* S(n-k)
Podemos continuar com a expansão
indefinidamente ou existe um limite para k?
O limite é o caso base S(1), ou seja,
n-k = 1
⇓
k = n-1

29. S(n) = 2
k
* S(n-k)
Podemos continuar com a expansão
indefinidamente ou existe um limite para k?
O limite é o caso base S(1), ou seja,
n-k = 1
⇓
k = n-1
⇓
S(n) = 2
n-1
* S[n-(n-1)] = 2
n-1
* S[1] = 2
n-1
* 2 = 2
n

30. Passo 3: Verificar
•Por raciocínio indutivo, inferimos que a
solução em forma fechada é S(n) = 2
n
.
•Ainda é preciso demonstrar que, de fato,
S(n) = 2
n
, para todo n ≥ 1.
‣podemos fazer isso por indução em n.

31. Estratégias para Resolução
de Recorrências
•Método “expandir, conjecturar e verificar”
•Solução geral
‣no caso de uma relação de recorrência linear de
primeira ordem.

32. Recorrência Linear
•Uma relação de recorrência para uma
seqüência S(n) é denominada linear se os
valores anteriores de S aparecem na relação
apenas na primeira potência.
•Forma geral:
‣S(n) = f1(n)S(n-1)+f2(n)S(n-2)+...+fk(n)S(n-k)+g(n)

33. Recorrência de
Primeira Ordem
•Uma relação de recorrência para uma
seqüência S(n) é de primeira ordem se o
cálculo do termo n depende apenas do
termo n-1.
•Forma geral:
‣S(n) = f1(n) S(n-1) + g(n)

34. Solução Geral
•Utilizando o método “expandir, conjecturar
e verificar”, podemos encontrar uma
solução em forma fechada geral para
relações de recorrência lineares de
primeira ordem com coeficientes
constantes.
•Solução geral para
‣
S(n)=cS(n−1) +g(n)
S(n)=c
n−1
S(1) +
n￿
i=2
c
n−i
g(i)

35. Exemplo
S(n)=cS(n−1) +g(n)
⇓
S(n)=2S(n−1)
c=2eg(n)=0
<z
S(n)=2
n−1
S(1) +
n
￿
i=2
2
n−1
0
=2
n−1
2+
n
￿
i=2
0=2
n−1
2+0=2
n
S(n)=c
n−1
S(1) +
n￿
i=2
c
n−i
g(i)
i

36. Métodos para resolver relações de recorrência
Método Passos “Expandir,
conjecturar e
verificar”
1.Expandir a recorrência até que seja possível
inferir um padrão;
2.Determinar o padrão para k = n-1;
3.Demonstrar a fórmula resultante por indução.
Solução Geral
1.Escrever a recorrência na forma
2.Substitua c, S(1) e g(n) na fórmula geral
3.Calcule o somatório para obter a fórmula final
S(n)=cS(n−1) +g(n)
S(n)=c
n−1
S(1) +
n￿
i=2
c
n−i
g(i)

37. Exemplo: Solução Geral
•Considere a seqüência T como definida a
seguir:
‣T(1) = 2
‣T(n) = T(n-1) + n + 1
•Encontre a solução em forma fechada para
a relação de recorrência, utilizando o
método da solução geral.