/Recorencia

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO CENTRO DE CIÊNCIAS AGRÁRIAS DEPARTAMENTO DE ENGENHARIA RURAL MATEMÁTICA DISCRETA LISTA DE EXERCÍCIOS - 2011/II

1. Escreva os 5 primeiros valores das seqüência: A(1) = 2 1 a) A(n) =

A(n − 1)

b) c) d) e) f)

B(0) = 1 B(n) = B (n -1) + n C(1) = 1 C(n) = C(n - 1) + n2 D(1) = 1 D(n) = D(n - 1) +

1 n

E(1) = 1 E(n) = n*E(n - 1) F(0) = 1 F(1) = 1 F(n) = F(n - 1) + F(n - 2) + 1

2. Tente encontrar uma fórmula fechada para cada seqüência do exercício anterior 3. Resolva cada uma das seguintes relações de recorrência fornecendo uma fórmula fechada A(0) = 3 a) A(n) = 10 * A(n - 1) B(0) = 5 b) B(n) = -B (n - 1) C(0) = 0 c) C(n) = 2*C(n - 1) + 2 D(0) = 0 d) D(n) = 4 - 2*D(n - 1) E(0) = 1 e) E(1) = 4 E(n) = 8*E(n - 1) - 15*E(n - 2) F(0) = 4 f) F(1) = 4 F(n) = F(n - 1) + 6*F(n - 2) 4. Prove por Indução que as fórmulas fechadas encontradas no exercício anterior são válidas 5. Prove por Indução que para qualquer n ∈ Ν : n a)

∑ 2i = n(n + 1) i =1

b) (n-1) + (n-2)+...+ 3 + 2 + 1 =

n(n − 1) 2

c)

∑

i(i + 1) n(n + 1)(n + 2) = 2 6 i =1 n(2n − 1)(2n + 1) 3

n

d) 1 + 8 + 27 + ... + n3 = (1 + 2 + ... + n)2 e) 12 + 32 + 52 + ... + (2n-1)2 = n f) g) h) i) j) k) l) m) n) o) p) q)

∑ (6i − 2) = n(3n + 1) i =1 n

∑ i(i + 1) = n + 1 i =1

1

n

1*1! + 2*2! + 3*3! + ... + n*n! = (n-1)! - 1 1*21 + 2*22 + 3*23 + ... + n*2n = (n-1)2n+1 + 2 n2 > n + 1, para n > 1 n2 > 5n + 10, para n > 6 2n+1 < 3n, para n > 1 n! > n2, para n > 4 23n-1 é divisível por 7 2n + (-1)n+1 é divisível por 3 n3 + 2n é divisível por 3 7n-2n é divisível por 5