Lista8 Recursividade

Prévia do material em texto

Lista 8 de Matemática Discreta I
Recursividade e recorrência
1. Ache f (1), f (2), f (3) e f (4) se f (n) é definido recursivamente por f (0) = 1 e para
n = 0, 1, 2, . . .
(a) f (n + 1) = f (n) + 2.
(b) f (n + 1) = 3 f (n).
(c) f (n + 1) = 2 f (n).
(d) f (n + 1) = f (n)2 + f (n) + 1.
2. Ache f (1), f (2), f (3), f (4) e f (5) se f (n) é definido recursivamente por f (0) = 3 e
para n = 0, 1, 2, . . .
(a) f (n + 1) = −2 f (n).
(b) f (n + 1) = 3 f (n) + 7.
(c) f (n + 1) = 3 f (n)/3.
(d) f (n + 1) = f (n)2 − 2 f (n) − 2.
3. Ache f (2), f (3), f (4) e f (5) se f (n) é definido recursivamente por f (0) = −1, f (1) = 2
e para n = 1, 2, . . .
(a) f (n + 1) = f (n) + 3 f (n − 1).
(b) f (n + 1) = f (n)2 f (n − 1).
(c) f (n + 1) = f (n − 1)/ f (n).
(d) f (n + 1) = 3 f (n)2 − 4 f (n − 1)2.
4. Ache f (2), f (3), f (4) e f (5) se f (n) é definido recursivamente por f (0) = f (1) = 1 e
para n = 1, 2, . . .
(a) f (n + 1) = f (n) − f (n − 1).
(b) f (n + 1) = f (n)/ f (n − 1).
(c) f (n + 1) = f (n − 1) f (n).
1
2
(d) f (n + 1) = f (n)2 + f (n − 1)3.
5. Determine quais das seguintes definições abaixo são definições recursivas válidas
de uma função f do conjunto de todos os inteiros não negativos para o conjunto
dos inteiros.
(a) f (0) = 0, f (n) = 2 f (n − 2) para n ≥ 1.
(b) f (0) = 1, f (n) = f (n − 1) − 1 para n ≥ 1.
(c) f (0) = 2, f (1) = 3, f (n) = f (n − 1) − 1 para n ≥ 2.
(d) f (0) = 1, f (1) = 2, f (n) = 2 f (n − 2) para n ≥ 2.
(e) f (0) = 1, f (n) = 3 f (n − 1) se n é ímpar e n ≥ 1 e f (n) = 9 f (n − 2) se n é par e
n ≥ 2.
6. Defina recursivamente a sequência {an} para n = 1, 2, 3, . . . se
(a) an = 6n.
(b) an = 2n + 1.
(c) an = 10n.
(d) an = 5.
(e) an = 4n − 2
7. Seja a função F(n) a soma dos n primeiros inteiros positivos. Defina F(n) recursi-
vamente.