Lista3-Respostas

Prévia do material em texto

Respostas da 3a Lista de Matema´tica Discreta
Raphael Lu´ıs Tavares Costa
28 de abril de 2011
Questa˜o 01
2 + 4 + 6 + ... + n = n ∗ (n + 1)
Passo Ba´sico: 2 = 1 ∗ (1 + 1) (OK)
A propriedade e´ va´lida para k≥ 1
Prova de que e´ va´lida para k+1:
2 + 4 + 6 + ... + 2k = k ∗ (k + 1)
2 + 4 + 6 + ... + 2k + 2k + 2 = k ∗ (k + 1) + 2k + 2
2 + 4 + 6 + ... + 2k + 2 ∗ (k + 1) = k ∗ (k + 1) + 2 ∗ (k + 1)
2 + 4 + 6 + ... + 2k + 2 ∗ (k + 1) = (k + 1) ∗ (k + 2) (Q.E.D.)
Questa˜o 02
1 + 4 + 7 + ... + (3 ∗ n− 2) = 2n ∗ (3 ∗ n− 1)
Passo Ba´sico: (3 ∗ 1− 2) = 2 ∗ 1 ∗ (3 ∗ 1− 1)
1 = 4? (A propriedade e´ falsa. Prova por contra-exemplo)
1
Questa˜o 03
1
1∗3 +
1
3∗5 +
1
5∗7 + ... +
1
(2∗n−1)∗(2∗n+1) =
1
2∗n+1
Passo Ba´sico: 1
1∗3 =
1
3
(OK)
A propeiedade e´ va´lida para k≥ 1
Prova de que e´ va´lida para k+1:
1
3
+ 1
15
+ 1
35
+ ... + 1
(2∗k−1)∗(2∗k+1) =
1
2∗k+1
1
3
+ 1
15
+ 1
35
+ ... + 1
(2∗k−1)∗(2∗k+1) +
1
(2∗(k+1)−1)∗(2∗(k+1)+1) =
1
2∗k+1 +
1
(2∗(k+1)−1)∗(2∗(k+1)+1)
1
3
+ 1
15
+ 1
35
+ ... + 1
(2∗k−1)∗(2∗k+1) +
1
(2∗(k+1)−1)∗(2∗(k+1)+1) =
1
2∗k+1 +
1
(2∗(k+1)−1)∗(2∗(k+1)+1)
↓ (MMC)
1
3
+ 1
15
+ 1
35
+ ... + 1
(2∗k−1)∗(2∗k+1) +
1
(2∗(k+1)−1)∗(2∗(k+1)+1) =
2∗k−3
(2∗(k+1)−1)∗(2∗(k+1)+1) +
1
(2∗(k+1)−1)∗(2∗(k+1)+1)
1
3
+ 1
15
+ 1
35
+ ... + 1
(2∗k−1)∗(2∗k+1) +
1
(2∗(k+1)−1)∗(2∗(k+1)+1) =
2∗(k−1)
(2∗k−1)∗(2∗k+3)
1
3
+ 1
15
+ 1
35
+ ... + 1
(2∗k−1)∗(2∗k+1) +
1
(2∗(k+1)−1)∗(2∗(k+1)+1) =
1
2∗k+3
1
3
+ 1
15
+ 1
35
+ ... + 1
(2∗k−1)∗(2∗k+1) +
1
(2∗(k+1)−1)∗(2∗(k+1)+1) =
1
2∗(k+1)+1
(Q.E.D.)
Questa˜o 04
12 + 22 + 32 + ... + n2 = n∗(n+1)∗(2n+1)
6
Passo Ba´sico: 12 = 1∗2∗3
6
(OK)
A propriedade e´ va´lida para k≥ 1
Prova de que e´ va´lida para k+1:
12 + 22 + 32 + ... + k2 = k∗(k+1)∗(2k+1)
6
12 + 22 + 32 + ... + k2 + (k + 1)2 = (k
2+k)∗(2k+1)
6
+ k2 + 2 ∗ k ∗ 1 + 12
12 + 22 + 32 + ... + k2 + (k + 1)2 = 2k
3+3k2+k
6
+ 6∗k
2+12k+6
6
12 + 22 + 32 + ... + k2 + (k + 1)2 = 2k
3+9k2+13k+6
6
12 + 22 + 32 + ... + k2 + (k + 1)2 = (k+1)∗(2k
2+7k+6)
6
12 + 22 + 32 + ... + k2 + (k + 1)2 = (k+1)∗(k+2)∗(2k+3)
6
12 + 22 + 32 + ... + k2 + (k + 1)2 = (k+1)∗((k+1)+1)∗(2(k+1)+1)
6
(Q.E.D.)
2
Questa˜o 05
23n − 1 = 7 ∗ x
Passo Ba´sico: 2(3 ∗ 1)− 1 = 7 (OK)
A propriedade e´ va´lida para k≥ 1
Prova de que e´ va´lida para k+1:
23k − 1 = 7 ∗ x
23 ∗ (23k − 1) = 56 ∗ x
23k+3 − 8 = 56 ∗ x
23(k+1) − 1 = 56 ∗ x + 7
23(k+1) − 1 = 7 ∗ (8 ∗ x + 1) (Q.E.D.)
Questa˜o 06
7n − 2n = 5 ∗ x
Passo Ba´sico: 71 − 21 = 5 (OK)
A propriedade e´ va´lida para k≥ 1
Prova de que e´ va´lida para k+1
7k − 2k = 5 ∗ x
7k+1 − 7 ∗ 2k = 35 ∗ x
2 ∗ 7k+1 − 7 ∗ 2k+1 = 70 ∗ x
2 ∗ 7k+1 − 2 ∗ 2k+1 − 5 ∗ 2k+1 = 70 ∗ x
↓ (Divide tudo por 2)
7k+1 − 2k+1 − 5 ∗ 2k = 35 ∗ x
7k+1 − 2k+1 = 35 ∗ x + 5 ∗ 2k
7k+1 − 2k+1 = 5 ∗ (7 ∗ x + 2k) (Q.E.D)
3
Questa˜o 07
72n + 16n− 1 = 64 ∗ x
Passo Ba´sico: 72 + 16− 1 = 64 (OK)
A propriedade e´ va´lida para k≥ 1
Prova de que e´ va´lida para k+1:
72k + 16k − 1 = 64 ∗ x
72k + 16(k + 1)− 1 = 64 ∗ x + 16
72k+2 + 49 ∗ 16(k + 1)− 49 = 64 ∗ 49 ∗ x + 16 ∗ 49
72(k+1) + 16(k + 1)− 1 = 64 ∗ 49 ∗ x + 16 ∗ 49 + 48− 48 ∗ 16(k + 1)
↓ (48 = 16 ∗ 3) e (48 = 4 ∗ 12)
72(k+1) + 16(k + 1)− 1 = 64 ∗ 49 ∗ x + 16 ∗ 49 + 16 ∗ 3− 64 ∗ 12(k + 1)
72(k+1) + 16(k + 1)− 1 = 64 ∗ 49 ∗ x + 16 ∗ 52− 64 ∗ 12(k + 1)
72(k+1) + 16(k + 1)− 1 = 64 ∗ 49 ∗ x + 64 ∗ 13− 64 ∗ 12(k + 1)
72(k+1) + 16(k + 1)− 1 = 64 ∗ (49 ∗ x + 13− 12 ∗ (k + 1)) (Q.E.D.)
Questa˜o 08
n3 − n = 3 ∗ x
Passo Ba´sico: 13 − 1 = 0 (0
3
= 0) (OK)
A propriedade e´ va´lida para k≥ 1
Prova de que e´ valida para k+1:
k3 − k = 3 ∗ x
k3 + 3k2 + 3k + 1− k − 1 = 3 ∗ x + 3k2 + 3k + 1− 1
(k + 1)3 − (k + 1) = 3 ∗ x + 3 ∗ k2 + 3k
(k + 1)3 − (k + 1) = 3 ∗ (x + k2 + k) (Q.E.D.)
Questa˜o 09
Passo Ba´sico: Quando se quer correr 3 milhas, se pode correr 1 milha e depois
mais duas. Quando se quer correr 4 milhas, se pode correr 2 milhas e depois
mais duas.
Passo Indutivo: Assumindo que a afirmac¸a˜o e´ verdade para n com 1 ≤
n ≤ k, deve-se provar que a afirmac¸a˜o tambe´m e´ verdade para n = k+1.
4
Considerando que a pessoa em questa˜o anda inicialmente uma quantidade
de milhas igual a x com 1 ≤ x ≤ k e que depois anda o resto da distaˆncia,
tem-se que agora ela deve percorrer a distaˆncia k + 1 − x e, como todas as
varia´veis sa˜o inteiras, 1 ≤ k + 1− x ≤ k e, logo, a pessoa pode andar o resto
do percurso.
Questa˜o 10
(a) P (18) = 7 + 7 + 4
P (19) = 4 + 4 + 4 + 7
P (20) = 4 + 4 + 4 + 4 + 4
P (21) = 7 + 7 + 7
(b) In´ıcio do Passo Indutivo: A Hipo´tese Indutiva diz que P(n) e´ va´lido
para todo 18 ≤ n ≤ k , k ≥ 21
(c) E´ necessa´rio provar, no Passo Indutivo, que a propriedade e´ va´lida para
(k+1)
(d) Fim do Passo Indutivo: Considerando (k + 1) > k e tendo provado a
propriedade para os primeiros 4 valores a partir de 18, tem-se que a
partir de qualquer um desses valores e´ poss´ıvel somar +4, tendo assim
18 + 4 = 22 ; 19 + 4 = 23 ; 20 + 4 = 24 e 21 + 4 = 25 adquirindo os
pro´ximos 4 vaores que podem ser formados. E a partir desses 4 pode-se
chegar aos pro´ximos 4 e assim por diante. Logo, para qualquer k ≥ 21
e´ poss´ıvel chegar a (k+1) apenas somando 4 a (k-3), para o qual a
propriedade ja´ e´ aceita.
(e) A propriedade so´ e´ va´lida para n ≥ 18 porque 18,19,20,21 e´ o primeiro
conjunto de nu´meros em sequeˆncia que podem ser criados usando ape-
nas fatores 4 e 7 positivos. (O nu´mero de selos tem que ser positivo).
(Q.E.D.)
5
Questa˜o 11
Resposta: Com notas de U$2,00 e U$5,00 e´ poss´ıvel criar qualquer montante
positivo de dinheiro com excessa˜o de U$1,00 e U$3,00.
Passo Ba´sico: Com uma nota de 2 tem-se o valor de U$2,00 e com
duas tem-se o valor de U$4,00. Com uma nota de 5 tem-se o valor de U$5,00.
Passo Indutivo: Assumindo a propriedade va´lida para 4 ≤ n ≤ k , k ≥ 5,
deve-se provar que a propriedade e´ va´lida para (k+1).
Sabendo que a propriedade e´ va´lida para k − 1 < k, tem-se que, ao
somar-se 2 a (k-1) chega-se a (k+1), provando a propriedade va´lida para
(k+1). (Q.E.D.)
6