Exercícios de Álgebra e Indução

Prévia do material em texto

Fund. de Álgebra: Exerćıcios 1, umas soluções
1. (a) Dê um exemplo expĺıcito para mostrar que a cota inferior de um
conjunto S ⊂ R limitado inferiormente não é única.
(b) Prove que quando um conjunto S ⊂ R tem menor elementos a, b,
então a = b (ou seja, o menor elemento é único).
R:
(a) S = N. −2, 0,−6 6 n ∀n ∈ N. Logo, todos deles são cotas inferiores
de N.
(b) a, b ∈ S dois menor elementos de S.
a menor elemento implica em particular que a 6 b já que b ∈ S.
b menor elemento implica em particular que b 6 a já que a ∈ S.
Mas a 6 b 6 a =⇒ a = b.
2. Use indução para provar que cada uma das afirmações abaixo é verdadeira.
(a)
∑n
i=1(4i + 1) = n(2n + 3).
(b)
∑n
i=1 i
3 = (
∑n
i=1 i)
2
(dica: use um exemplo das aulas).
(c) 8n−3n é múltiplo de 5 para todo n ∈ Z+ (truque: −8·3k+8·3k = 0).
(d) Se a, b são inteiros com a − b 6= 0 então an − bn é múltiplo de a − b
para todo n ∈ Z+.
R: (só parte (a))
(a) Caso base (n = 1):
∑1
i=1(4i + 1) = 4 + 1 = 5 = 1(2 · 1 + 3).
Etapa de indução: Hipótese de indução:
∑k
i=1(4i + 1) = k(2k + 3).
Queremos mostrar que
∑k+1
i=1 (4i + 1) = (k + 1)(2(k + 1) + 3).
k+1∑
i=1
(4i + 1) =
(
k∑
i=1
(4i + 1)
)
+ 4(k + 1) + 1
= k(2k + 3) + 4(k + 1) + 1 (pela HI)
= 2k2 + 3k + 4k + 4 + 1
= 2k2 + 7k + 5
= (k + 1)(2k + 5)
= (k + 1)(2k + 2 + 3)
= (k + 1)(2(k + 1) + 3).
1
3. Prove duas partes da Questão 2 por usando o Prinćıpio da boa ordenação.
R: (só parte (a))
(a) Seja
S =
{
n |n > 1 e
n∑
i=1
(4i + 1) 6= n(2n + 3)
}
.
Queremos mostrar que S = ∅. Vamos supor (para ganhar con-
tradição) que S 6= ∅. Já que S é limitado inferiormente, temos pelo
prinćıpio da boa ordenação que S contem um menor elemento m.
Observe que m 6= 1 já que
∑1
i=1(4i + 1) = 4 + 1 = 5 = 1(2 · 1 + 3).
Logo, podemos considerar m− 1, e temos (já que m é minimal) que
m−1∑
i=1
(4i + 1) = (m− 1)(2(m− 1) + 3).
Agora
m∑
i=1
(4i + 1) =
(
m−1∑
i=1
(4i + 1)
)
+ 4m + 1
= (m− 1)(2(m− 1) + 3) + 4m + 1
= . . . calculações . . .
= m(2m + 3).
Segue que m 6∈ S - uma contradição, pois m ∈ S. Logo, nossa
suposição que S 6= ∅ era falsa. Ou seja, S = ∅.
4. Considere a matriz
A =
(
1 1
0 1
)
.
(a) Calcule A2, A3 e conjeture (= adivinhe) a forma geral pra matriz An
(n > 1).
(b) Use indução para provar que a sua conjetura é verdadeira.
(c) Repita partes (a), (b) pra matriz
B =
1 1 10 1 1
0 0 1
 .
R: Nossa conjetura deve ser que
An =
(
1 n
0 1
)
.
Demonstração: Caso base (n = 1) claramente vale.
Hipótese de indução:
Ak =
(
1 k
0 1
)
.
2
Queremos mostrar que
Ak+1 =
(
1 k + 1
0 1
)
.
Mas
Ak+1 = A ·Ak =
(
1 1
0 1
)(
1 k
0 1
)
=
(
1 k + 1
0 1
)
.
Pronto.
Parte (c): A resposta é
Bn =
1 n ∑ni=1 i0 1 n
0 0 1
 .
Mostre que o resultado vale no mesmo jeito como pro matriz A.
5. Seja Ln o poĺıgono convexo com n lados (ex L3 é um triângulo, L4 é um
quadrado, L5 é um pentágono etc.). Mostre por indução que para todo
n > 3, Ln tem
n(n−3)
2 diagonais.
R: Melhor fazer esta questão com diagramas. O caso base é o triângulo,
que possui 0 diagonais. Já que 3·02 = 0, o resultado vale.
Estapa de indução. HI: Lk tem
k(k−3)
2 diagonais. Considere Lk+1. Remove
um vertice de Lk+1 por conetando dois vertices de distância 2. Ganhamos
uma cópia de Lk.
Os diagonais de Lk+1 são:
• Os diagonais de Lk (k(k−3)2 pela HI)
• Os diagonais começando no vertice que removeu (k − 2)
• O diagonal que removeu para ganhar Lk (1)
Somando estes números, o resultado segue.
6. Encontre o erro na seguinte “prova”que em qualquer grupo com n pessoas,
todas elas têm a mesma idade.
Se um grupo consiste de uma pessoa, todas têm a mesma idade.
Suponha que em qualquer grupo com k pessoas, todas têm a mesma idade.
Sejam a1, a2, ..., ak+1 as pessoas em um grupo com k + 1 pessoas.
Desde que as pessoas a1, a2, ..., ak e a2, a3, ..., ak+1 formam grupos com k
pessoas, todas elas têm a mesma idade, por hipótese de indução.
Desde que a2 está em cada um destes grupos, segue que todas as k + 1
pessoas a1, a2, ..., ak+1 têm a mesma idade.
R: O problema é que a etapa de indução não vale quando k + 1 = 2:
considere um conjunto {a1, a2}. Os dois subconjuntos do argumento são
{a1}, {a2}. Mas não temos um elemento que pertence aos dois subconjun-
tos.
3
7. Considere a, b, c, d inteiros não nulos. Verifique se é verdadeiro ou falso,
justificando.
(a) Se d|a e d|b então d2|ab.
(b) a|c e b|d então (a + b)|(c + d).
(c) a|c e b|d então ab|cd.
(d) (a + b)|(c + d) então a|c e b|d.
(e) d|a e d|b então d|(a2 + b2).
(f) d|(a9 − b) e d|a então d|b.
R:
(a) V: d|a, d|b implicam que a = qd, b = rd (alguns q, r). Logo ab =
qdrd = d2qr, que implica que d2|ab.
(b) F: contraexemplo a = b = c = 1, d = 2. a|c, b|d, mas
a + b = 1 + 1 = 2 6 | 3 = 1 + 2 = c + d.
(c) V.
(d) F.
(e) V.
(f) V.
8. Prove que se a é um inteiro que não é um múltiplo de 3 então 3|(a2 − 1).
R: 3 6 | a =⇒ a = 3k + 1 ou a = 3k + 2 (algum k). De um exemplo das
aulas, sabemos que em todo caso a2 = 3k′ + 1 (algum k). Logo
a2 − 1 = 3k′ + 1− 1 = 3k′,
ou seja, 3|(a2 − 1).
9. Mostre que o quadrado de qualquer número inteiro ı́mpar é da forma 8k+1.
R: Um inteiro ı́mpar a tem a forma a = 2m + 1 (algum m). Logo
a2 = (2m + 1)2 = 4m2 + 4m + 1 = 4m(m + 1) + 1.
Mas um dos números m,m + 1 é par, então m(m + 1) = 2k (algum k).
Agora
a2 = 4m(m + 1) + 1 = 8k + 1.
10. Seja a um inteiro que deixa resto 3 na divisão por 6. Mostre que
72 | (a2 − 9).
R: a = 6q + 3. Agora
a2 − 9 = (6q + 3)2 − 9 = 36q2 + 36q + 9− 9 = 36q(q + 1) = 72k
já que q(q + 1) é par como na resposta anterior.
4
11. Determine os inteiros positivos que divididos por 17 deixam um resto igual
ao quadrado do quociente.
R: Estamos procurando os a ∈ Z+ tais que a = 17q + q2. Já que q2 6 17,
temos q = 0, 1, 2, 3, 4. Só analise os cinco casos. Por exemplo,
q = 3 : a = 17q + q2 = 17 · 3 + 32 = 60.
12. (a) Um número inteiro a é ı́mpar e deixa resto 2 na divisão por 3. Qual
é o resto da divisão de a por 6?
(b) Um número inteiro a é par mas não é múltiplo de 4. Qual é o resto
da divisão de a2 + 12 por 16?
R:
(a) Temos a = 2k + 1, a = 3m + 2 (alguns k,m). Logo
2k = 3m + 1.
Observe que m precisa de ser ı́mpar, pois 3m + 1 é par. Escreve
m = 2t + 1 (algum t). Logo
a = 3m + 2 = 3(2t + 1) + 2 = 6t + 3 + 2 = 6t + 5,
e o resto da divisão de a por 6 é 5.
(b) a é par mas não é múltiplo de 4, logo a = 4k + 2 (algum k).
a2 + 12 = (4k + 2)2 + 12 = 16k2 + 16k + 4 + 12 = 16(k2 + k + 1)
logo 16|(a2 + 12), ou seja, o resto da divisão por 16 é 0.
5