MAT01375 - MATEMÁTICA DISCRETA B Eduardo Brietzke Lista 3

Prévia do material em texto

MAT 01375 – Matemática Discreta B – 2019/2 – Lista 3
1. Seja N0 = {0, 1, 2, 3, . . .}. Prove por indução:
a) (∀n ∈ N0)[ 8 | (32n + 7) ]
b) (∀n ∈ N0)[ 13 | (92n − 24n) ]
c) (∀n ∈ N0)[ 14 | (34n+2 + 52n+1) ]
d) (∀n ∈ N0)[ 9 | (10n + 3 · 4n+2 + 5) ]
e) (∀n ∈ N0)[ 169 | (33n+3 − 26n+ 27) ]
2. Mostre, por indução, que para todo a ∈ N0
a) 2 | a2 − a b) 3 | a3 − a c) 5 | a5 − a d) 7 | a7 − a
Observação: 1) As afirmações acima são casos particulares do Pequeno Teorema de Fer-
mat, que afirma que se p é primo, então (∀a ∈ N0)[ p | (ap − a)] .
2) Por exemplo, p = 4 não é primo, para a = 2, 4 - (24 − 2).
3) 561 = 3 · 11 · 17 é composto mas mostra-se que 561 | (a561 − a) para todo a ∈ N0
(dizemos que 561 é um número de Carmichael).
3. Mostre por indução:
a) (∀n ∈ N)
[
13 + 23 + 33 + · · ·+ n3 = n
2(n+ 1)2
4
]
b) (∀n ∈ N)
[
1 · 3 + 2 · 4 + · · ·+ n(n+ 2) = n(n+ 1)(2n+ 7)
6
]
c) (∀n ∈ N)
[
1 · 2 · 3 + 2 · 3 · 4 + · · ·+ n(n+ 1)(n+ 2) = n(n+ 1)(n+ 2)(n+ 3)
4
]
d) (∀n ∈ N)
[
1 · 1! + 2 · 2! + 3 · 3! + · · ·+ n · n! = (n+ 1)!− 1
]
e) (∀n > 4) (n! > 2n )
f) (∀n ≥ 9) (n! > 4n )
4. Para n ∈ N, seja Sn = 1 + 2 + 3 + · · · + n. Considere a proposição (que é falsa)
(∀n ∈ N)
[
Sn =
(2n+ 1)2
8
]
.
Encontre o erro na seguinte “prova”da proposição: suponhamos, por hipótese de indução,
que a igualdade seja válida para um certo número natural n, ou seja, que vale Sn =
1+2+3+ · · ·+n = (2n+ 1)
2
8
. Mostremos que a igualdade também é vá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 Método de Indução, Sn = 1 + 2 + 3 + · · · + n =
(2n+ 1)2
8
, para qualquer
n ≥ 1.