L9D131

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2013/1
Lista de Exerc´ıcios 9
1. Utilize uma versa˜o conveniente do Princ´ıpio de Induc¸a˜o Matema´tica para
demonstrar os seguintes resultados.
(a) Para todo n ≥ 0, 11n − 5n e´ divis´ıvel por 6.
(b) Para todo n ≥ 0, 8 | (32n + 7)
(c) Para todo n ≥ 0, 9 | (10n + 3 · 4n+2 + 5)
(d) Para todo n ≥ 1,
1
1 · 3 +
1
3 · 5 +
1
5 · 7 + · · ·+
1
(2n− 1) · (2n+ 1) =
n
2n+ 1
.
(e) Para todo n ≥ 1, temos
n∑
i=1
i3 = 13 + 23 + · · ·+ n3 = (1 + 2 + · · · + n)2 =
(
n∑
i=1
i
)2
=
(
n(n+ 1)
2
)2
.
(f) Para todo n ≥ 0, temos
n∑
i=0
i
(
n
i
)
= n2n−1.
(g) Para todo n ≥ 5, vale que 2n > n2.
(h) Para todo n ≥ 1,
n∑
k=1
1
k(k + 1)
=
1
1 · 2 +
1
2 · 3 + · · ·+
1
n(n+ 1)
=
n
n+ 1
.
(i) Para todo n ≥ 1,(
1− 1
2
)(
1− 1
4
)(
1− 1
8
)
· · ·
(
1− 1
2n
)
≥ 1
4
+
1
2n+1
.
3. Prove que todo inteiro positivo pode ser escrito como a soma de poteˆncias
distintas de 2.
4. Quem e´ maior n2 ou 3n ? Fac¸a uma conjectura e demonstre-a por induc¸a˜o.
5. Utilizando o fato de que cos(a + b) = cos a cos b − sen a sen b e sen(a + b) =
sen a cos b+sen b cos a, demonstre a Fo´rmula de De Moivre para todo inteiro n ≥ 1
e todo θ ∈ R:
(cos θ + i sen θ)n = cos(nθ) + i sen(nθ),
onde i denota o nu´mero imagina´rio i =
√−1.
6. A sequeˆncia de Fibonacci e´ definida por F0 = 0, F1 = 1 e Fn = Fn−1 + Fn−2
para n ≥ 2. Demonstre os seguintes fatos:
(a)
∑
n
i=0
Fi = Fn+2 − 1.
(b) 2Fn+2 = Fn+3 + Fn.
(c) Entre dois elementos pares consecutivos na sequeˆncia, F (n) ha´ exatamente
dois elementos ı´mpares.
(d) Dois elementos consecutivos na sequeˆncia sa˜o sempre primos entre si. (Isto
e´, o seu ma´ximo divisor comum e´ 1.)
7. Afirmac¸a˜o: (∀n ≥ 1) Sn = 1 + 2 + 3 + · · ·+ n = (2n+ 1)
2
8
.
Encontre o erro na seguinte “prova” : suponhamos, por hipo´tese de induc¸a˜o,
que a fo´rmula seja va´lida para um certo nu´mero natural n, ou seja, que vale
Sn = 1+ 2 + 3+ · · ·+ n = (2n+ 1)
2
8
. Mostremos que a fo´rmula tambe´m e´ va´lida
para n+ 1. De fato:
Sn+1 = Sn + (n+ 1) =
(2n+ 1)2
8
+ (n+ 1) =
4n2 + 4n+ 1
8
+ (n+ 1) =
=
4n2 + 4n+ 1 + 8n+ 8
8
=
4n2 + 12n+ 9
8
=
(2n+ 3)2
8
=
(2(n+ 1) + 1)2
8
.
Logo, pelo Princ´ıpio de Induc¸a˜o, Sn = 1+ 2 + 3 + · · ·+ n = (2n+ 1)
2
8
, para cada
n ≥ 1.