md_LE4

Prévia do material em texto

LISTA DE EXERCÍCIOS 4
UFMG/ICEx/DCC Matemática Discreta
Graduação em Ciência da Computação 2o Semestre de 2011
1. Prove por indução matemática que
12 + 22 + . . .+ n2 =
n(n+ 1)(2n+ 1)
6
, n ≥ 1.
2. Prove por indução matemática que
1 + 3 + 5 + . . .+ (2n− 1) = n2, n ≥ 1.
3. Prove por indução matemática que
13 + 23 + . . .+ n3 = (1 + 2 + . . .+ n)2, n ≥ 1.
4. Prove por indução matemática que
2 · 1 + 2 · 2 + 2 · 3 + . . .+ 2n = n2 + n, n ≥ 1.
5. Prove por indução matemática que
n−1∑
i=1
i(i+ 1) =
n(n− 1)(n+ 1)
3
,∀ inteiros n ≥ 2.
6. Ache a fórmula fechada para o produto(
1− 1
2
)(
1− 1
3
)(
1− 1
4
)
. . .
(
1− 1
n
)
∀ inteiros n ≥ 2 e prove o seu resultado por indução matemática.
7. Ache a fórmula fechada para a soma
1
1 · 3 +
1
3 · 5 + . . .+
1
(2n− 1) · (2n+ 1)
∀ inteiros n ≥ 1 e prove o seu resultado por indução matemática.
8. Ache a fórmula fechada para a soma
n∑
i=2
1
(i− 1)i ,
∀ inteiros n ≥ 2 e prove o seu resultado por indução matemática.
9. Suponha que temos selos de 4 e 7 centavos. Prove que é possível ter qualquer valor de postagem de 18
centavos ou mais usando somente esses selos.
10. Prove por indução matemática que n2 < 2n, para todos inteiros n ≥ 5.
11. Seja a seqüência a1, a2, a3, . . . definida como
a1 = 3
ak = 7ak−1,∀ inteiros k ≥ 2
Prove por indução matemática que an = 3 · 7n−1 para todos os inteiros n ≥ 1.
1
12. Seja a seqüência a1, a2, a3, . . . definida como
a1 = 1
a2 = 3
ak = ak−2 + 2ak−1,∀ inteiros k ≥ 3
Prove por indução matemática que an é ímpar para todos os inteiros n ≥ 1.
13. Seja a seqüência g0, g1, g2, . . . definida como
g0 = 12
g1 = 29
gk = 5gk−1 − 6gk−2,∀ inteiros k ≥ 2
Prove por indução matemática que gn = 5 · 3n + 7 · 2n para todos os inteiros n ≥ 0.
14. Seja a seqüência h0, h1, h2, . . . definida como
h0 = 1
h1 = 2
h2 = 3
hk = hk−1 + hk−2 + hk−3,∀ inteiros k ≥ 3
Prove por indução matemática que hn ≤ 3n para todos os inteiros n ≥ 0.
15. Seja a seqüência x0, x1, x2, . . . definida como
x0 = 0
x1 = 1
xk = 5x3k−1 + 7xk−2,∀ inteiros k ≥ 2
Prove por indução matemática que se k é múltiplo de 3 então xk é par.
16. Seja a seqüência a0, a1, a2, . . . definida como
a0 = 0
a1 = 0
ak = ak−1 + 3k(k − 1),∀ inteiros k ≥ 2
Ache a fórmula fechada para o k-ésimo termo e prove por indução matemática.
17. Seja a seqüência a0, a1, a2, . . . definida como
a0 = 0
a1 = 1
ak = k − ak−1,∀ inteiros k ≥ 1
Ache a fórmula fechada para o k-ésimo termo e prove por indução matemática.
18. Prove por indução matemática que ∀n ≥ 1, 3n − 2 é ímpar.
2