Lista08_InducaoFracaForte-BoaOrdenacao[solucao]

Prévia do material em texto

Área de Teoria DCC/UFMG Introdução à Lógica Computacional 2019/02
SOLUÇÃO DE LISTA DE EXERCÍCIOS
Lista 08
(Indução Fraca e Forte, Boa Ordenação)
Leitura necessária:
• Matemática Discreta e Suas Aplicações, 6a Edição (Kenneth H. Rosen):
– Caṕıtulo 4.1: Indução Matemática
– Caṕıtulo 4.2: Indução Completa e Boa Ordenação
Revisão.
1. Responda formalmente as seguintes perguntas:
(a) Explique o que é o prinćıpio da boa-ordenação.
Solução do professor: O prinćıpio da boa ordenação ou prinćıpio da boa ordem diz que todo
subconjunto não-vazio formado por números naturais possui um menor elemento.
Exerćıcios.
2. (Rosen 4.1.3) Seja P (n) a afirmação de que 12 + 22 + · · · + n2 = n(n + 1)(2n + 1)/6 para o inteiro
positivo n.
(a) Qual é a afirmação P (1)?
Solução do professor: A afirmação P (1) é de que 12 = 1(1 + 1)(2 · 1 + 1)/6, ou seja, de que
12 = 1(2)(3)/6.
(b) Mostre que P (1) é verdadeiro, completando o passo base da demonstração.
Solução do professor: P (1) é verdadeiro porque o lado esquerdo da igualdade e o direito são
ambos iguais a 1.
(c) Qual é a hipótese de indução?
Solução do professor: A hipótese de indução é que P (k) é válido para um inteiro positivo
qualquer, ou seja, que
12 + 22 + · · ·+ k2 = k(k + 1)(2k + 1)
6
.
(d) O que você precisa demonstrar no passo indutivo?
1
Solução do professor: No passo indutivo preciso demonstrar que se P (k) é verdadeiro para
um k arbitrário, então P (k + 1) também é verdadeiro.
Ou seja, tenho que mostrar que
12 + 22 + · · ·+ k2 + (k + 1)2 = (k + 1)((k + 1) + 1)(2(k + 1) + 1)
6
=
(k + 1)(k + 2)(2k + 3)
6
.
(e) Complete o passo indutivo.
Solução do professor:
12 + 22 + · · ·+ k2 + (k + 1)2 =
(
k(k + 1)(2k + 1)
6
)
+ (k + 1)2 (pela I.H.)
=
k(k + 1)(2k + 1) + 6(k + 1)2
6
=
(k + 1)(k(2k + 1) + 6(k + 1))
6
(pondo (k + 1) em evidência)
=
(k + 1)(2k2 + 7k + 6)
6
=
(k + 1)(k + 2)(2k + 3)
6
(fatorando (2k2 + 7k + 6))
(f) Explique por que os passos acima mostram que a fórmula é verdadeira para todo inteiro positivo
n.
Solução do professor: Os passos acima mostram que a fórmula é verdadeira para todo inteiro
positivo n porque completamos com sucesso a demonstração por indução matemática: demons-
tramos o passo base, e demonstramos o passo indutivo.
3. (Rosen 4.1.6) Demonstre que 1 · 1! + 2 · 2! + · · ·+ n · n! = (n+ 1)!− 1, para todo inteiro positivo n.
Solução do professor: Por indução.
Passo base.
1 · 1! = (1 + 1)!− 1
Passo indutivo. Assumamos como hipótese de indução que para algum k ≥ 1 arbitrário tenhamos
que 1 · 1! + 2 · 2! + . . .+ k · k! = (k+ 1)!− 1. Queremos mostrar que nesse caso temos necessariamente
que 1 · 1! + 2 · 2! + . . .+ k · k! + (k + 1) · (k + 1)! = (k + 2)!− 1. Para isto podemos fazer:
1 · 1! + · · ·+ k · k! + (k + 1) · (k + 1)! = (k + 1)!− 1 + (k + 1) · (k + 1)! (pela I.H.)
= (1 + (k + 1))(k + 1)!− 1
= (k + 2)!− 1
2
4. (Rosen 4.1.11) Encontre uma fórmula para 1/2 + 1/4 + 1/8 + · · · + 1/2n examinando os valores dessa
expressão para pequenos valores de n e prove que a fórmula está correta.
Solução do professor: Vamos chamar de f(n) a fórmula 12 +
1
4 +
1
8 + · · ·+
1
2n . Nesse caso:
f(1) =
1
2
f(2) =
1
2
+
1
4
=
3
4
f(3) =
1
2
+
1
4
+
1
8
=
7
8
f(4) =
1
2
+
1
4
+
1
8
+
1
16
=
15
16
Neste ponto, conjecturamos que f(n) = 2
n−1
2n , para todo n ≥ 1.
Vamos demonstrar por indução que a conjectura está correta.
Demonstração. Seja P (n) a proposição “12 +
1
4 +
1
8 + · · ·+
1
2n =
2n−1
2n ”.
Passo base. P (1) é verdadeiro porque
f(1) =
21 − 1
21
=
1
2
.
Passo indutivo. A hipótese de indução é que P (k) seja verdadeiro para um inteiro k ≥ 1 arbitrário.
Então podemos derivar que P (k + 1) também é verdadeiro assim:
f(k + 1) =
1
2
+
1
4
+
1
8
+ · · ·+ 1
2k
+
1
2k+1
=
2k − 1
2k
+
1
2k+1
(I.H.)
=
2(2k − 1) + 1
2k+1
=
2k+1 − 1
2k+1
de onde conclúımos que P (k + 1) também é verdadeiro.
5. (Rosen 4.1.21) Demonstre que 2n > n2 para n ≥ 5, n inteiro.
Solução do professor: Por indução.
Passo base.
25 = 32 > 25 = 52
3
Passo indutivo.
2n+1 = 2 · 2n
≥ 2 · n2 (hip. indução)
≥ n2 + 2n+ 1 (para todo n ≥ 5, n2 ≥ 2n+ 1)
= (n+ 1)2
6. (Rosen 4.1.33) Demonstre que 5 divide n5 − n sempre que n é um inteiro não-negativo.
Solução do professor: Por indução.
Passo base. 0 divide 05 − 0 = 0.
Passo indutivo. Assumimos como hipótese de indução que para um k ≥ 0 arbitrário, k5 − k = 5m
para algum m inteiro. Queremos mostrar que (k + 1)5 − (k + 1) = 5m′ para algum m′ inteiro.
Para isso podemos fazer:
(k + 1)5 − (k + 1) = (k5 + 5k4 + 10k3 + 10k2 + 5k + 1)− (k + 1) (produto notável)
= (k5 − k) + (5k4 + 10k3 + 10k2 + 5k) (reagrupando parecelas)
= 5m+ 5(k4 + 2k3 + 2k2 + k) (pela hip. de indução)
= 5(m+ k4 + 2k3 + 2k2 + k) ,
de onde conclúımos que (k + 1)5 − (k + 1) também é diviśıvel por 5.
7. (Rosen 4.1.56) Demonstre que ¬(p1 ∨ p2 ∨ . . . ∨ pn) ≡ ¬p1 ∧ ¬p2 ∧ . . . ∧ ¬pn, para todo n ≥ 1. (Dica:
use a lei de De Morgan que diz que ¬(p ∨ q) ≡ ¬p ∧ ¬q.)
Solução do professor: Por indução.
Passo base.
¬p1 = ¬p1
Passo indutivo.
¬(p1 ∨ p2 ∨ . . . ∨ pk ∨ pk+1) = ¬((p1 ∨ p2 ∨ . . . ∨ pk) ∨ pk+1) (pela associatividade da disjunção)
= ¬(p1 ∨ p2 ∨ . . . ∨ pk) ∧ ¬pk+1 (por De Morgan)
= ¬p1 ∧ ¬p2 ∧ . . . ∧ ¬pk ∧ ¬pk+1 (pela hipótese de indução)
8. (Rosen 4.2.3) Seja P (n) a proposição “uma postagem de n centavos pode ser formada utilizando apenas
selos de 3 centavos e selos de 5 centavos”. Esse exerćıcio ilustra uma demonstração por indução forte
de que P (n) é verdade para n ≥ 8.
(a) Mostre que as proposições P (8), P (9) e P (10) são verdadeiras, completando o passo base da
demonstração.
4
Solução do professor: P (8) é verdadeiro porque podemos completar 8 centavos juntando um
selo de 3 centavos e um selo de 5 centavos.
P (9) é verdadeiro porque podemos completar 9 centavos juntando três selos de 3 centavos.
P (10) é verdadeiro porque podemos completar 10 centavos juntando dois selos de 10 centavos.
(b) Qual é a hipótese indutiva da demonstração?
Solução do professor: A hipótese indutiva é que P (i) vale para todo i entre 8 e k.
Matematicamente:
P (8) ∧ P (9) ∧ . . . ∧ P (k)
(c) O quê você necessita demonstrar no passo indutivo?
Solução do professor: Necessito demonstrar que se todas as postagens entre 8 centavos e k
centavos podem ser formadas usando apenas selos de 3 centavos e selos de 5 centavos, então uma
postagem de k + 1 centavos também pode ser obtida usando apenas selos de 3 centavos e de 5
centavos.
Matematicamente, tenho que mostrar que
[P (8) ∧ P (9) ∧ . . . ∧ P (k)]→ P (k + 1).
(d) Complete o passo indutivo para k ≥ 10.
Solução do professor: Se k ≥ 10, então k − 2 ≥ 8 e a hipótese de indução nos garante que
uma postagem de k− 2 centavos pode ser formada usando apenas selos de 3 e 5 centavos. Então,
para obter uma postagem de k + 1 centavos, basta adicionar um selo de 3 centavos à postagem
utilizada para k − 2 centavos.
(e) Explique porque estes passos mostram que a proposição é verdadeira sempre que n ≥ 8.
Solução do professor: Os passos mostram que a proposição é verdadeira porque completa-
mos o passo base e o passo indutivo da demonstração por indução, e pelo prinćıpio da indução
matemática forte a proposição é válida para todo inteiro positivo a partir de 8.
9. (Rosen 4.2.12) Utilize indução forte e mostre que todo inteiro positivo n pode ser escrito como a soma
de potências de 2 distintas, ou seja, como a soma de um subconjunto dos inteiros 20, 21 , 22, .... (Dica:
no passo indutivo, considere separadamente os casos k + 1 ı́mpar ou par. Note que (k+1)/2 é inteiro
quando k + 1 é par.)
Solução do professor: Queremos mostrar que para todo n > 0 temos
n =
∞∑
i=0
ai2
i,
onde cada ai, para i ∈ {0, 1, 2 . . .} assume o valor 0 ou o valor 1.
Passo base. Quando n = 1, temos 1 = 20 =
∑0
i=0 1 · 20.
5
Passorecursivo. Assuma que todo inteiro menor ou igual a k pode ser escrito como a fórmula
assim. Há dois casos posśıveis para k + 1:
• Se k + 1 é par, k + 1 = 2 · k′ para algum k′ ≤ k. Pela hipótese de indução, k′ pode ser escrito
como k′ =
∑∞
i=0 ai2
i. Logo:
k + 1 = 2 · k′ (k + 1 é par)
= 2 ·
∞∑
i=0
ai2
i (hip. ind.)
=
∞∑
i=0
ai2
i+1
=
∞∑
i=1
bi2
i (fazendo bi = ai+1)
=
∞∑
i=0
bi2
i (fazendo b0 = 0)
• Se k+ 1 é ı́mpar, k+ 1 = 1 + 2k′ para algum k′ ≤ k. Pela hipótese de indução, k′ pode ser escrito
como k′ =
∑∞
i=0 ai2
i. Logo:
k + 1 = 1 + 2k′ (k + 1 é ı́mpar)
= 1 + 2 ·
∞∑
i=0
ai2
i (hip. ind.)
= 1 +
∞∑
i=0
ai2
i+1
= 1 +
∞∑
i=1
bi2
i (fazendo bi = ai+1)
=
∞∑
i=0
bi2
i (fazendo b0 = 1)
10. Considere uma barra de chocolate formada por uma única fileira de n quadradinhos como na figura
abaixo.
1 2 3 · · · n−1 n
Suponha que você queira separar todos os quadradinhos da barra, de forma a obter n quadradinhos
individuais. Assuma que você pode realizar quebras na barra apenas entre dois quadradinhos con-
secutivos (i.e., você não pode partir um quadradinho no meio, apenas separar um quadradinho do
outro).
Usando indução forte, demonstre que para qualquer barra de n quadradinhos são necessárias exata-
mente n− 1 quebras para separar todos os quadradinhos.
Solução do professor: Queremos demonstrar que ∀n ∈ Z+ : P (n), onde P (n) é o predicado
“Toda barra de chocolate de n quadradinhos enfileirados pode ser separada em n quadradinhos usando
exatamente n− 1 quebras”. Vamos demonstrar por indução forte.
Passo base. P (1) é verdadeiro, pois nenhuma quebra é necessária para separar uma barra de apenas
1 quadradinho.
6
Passo indutivo. Assuma como hipótese de indução que para um k arbitrário P (j) seja verdadeiro
para todo 1 ≤ j ≤ k. Queremos mostrar que P (k + 1) também é verdadeiro. Nesse caso, note que
para qualquer barra de k+ 1 quadradinhos, precisamos fazer uma primeira quebra para produzir uma
sub-barra de j quadradinhos e uma outra sub-barra de k+ 1− j quadradinhos (1 ≤ j ≤ k). Pela I.H.,
a sub-barra de j quadradinhos pode ser separada usando mais j−1 quebras, e a sub-barra de k+1− j
quadradinhos pode ser separada usando (k + 1 − j) − 1 = k − j quebras. Logo, o número total de
quebras necessário para a barra de tamanho k + 1 é exatamente 1 + (j − 1) + (k − j) = k quebras.
Logo P (k + 1) também é verdadeiro, e a demonstração por indução está conclúıda.
11. Os números de Fibonacci, f0, f1, f2, ... são definidos recursivamente como a seguir:
f0 = 0,
f1 = 1,
fn = fn−1 + fn−2, para n = 2, 3, 4, ....
Em particular, os primeiros números de Fiboacci são
f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5,
f6 = 8, f7 = 13, f8 = 21, f9 = 34, f10 = 55, . . .
Utilize indução forte para mostrar que
fn =
1√
5
φn − 1√
5
ψn,
para n = 0, 1, 2, ..., onde φ = 1+
√
5
2 ≈ 1.61803398 (a “proporção divina”) e φ =
1−
√
5
2 ≈ −0.61803398.
Solução do professor:
Passo base. Temos que mostrar que a proposição é válida para f0 e f1.
f0 =
1√
5
φ0 − 1√
5
ψ0
=
1√
5
· 1− 1√
5
· 1
= 0
f1 =
1√
5
φ1 − 1√
5
ψ1
=
1 +
√
5
2
√
5
− 1−
√
5
2
√
5
=
2
√
5
2
√
5
= 1
7
Passo indutivo. Temos que mostrar que se a proposição é válida para 0, 1, . . . , n, então ela é válida
para n+ 1.
fn+1 = fn + fn−1 (pela def. de Fibonacci)
=
[
1√
5
φn − 1√
5
ψn
]
+
[
1√
5
φn−1 − 1√
5
ψn−1
]
(pela hip. de indução)
=
1√
5
φn−1 (φ+ 1)− 1√
5
ψn−1 (ψ + 1) (reagrupando os termos)
(1)
Mas verifica-se facilmente que:
φ+ 1 = φ2 (2)
e que
ψ + 1 = ψ2 (3)
Logo, podemos substituir (2) e (3) em (1) para obter:
fn+1 =
1√
5
φn−1φ2 − 1√
5
ψn−1ψ2
=
1√
5
φn+1 − 1√
5
ψn+1.
12. Encontre o erro na “demonstração” por indução abaixo da afirmação de que em qualquer grupo de n
pessoas, com n ≥ 1, todas têm a mesma cor de olhos.
“Demonstração”. Seja P (n) o predicado “Em qualquer grupo de n pessoas, todas têm a mesma cor
de olhos”. Queremos mostrar que P (n) é verdadeiro para todo inteiro n ≥ 1.
Passo base. P (1) é verdade porque em qualquer grupo de 1 pessoa, essa pessoa tem a mesma cor
de olhos que ela mesma.
Passo indutivo. Assuma como hipótese de indução que P (k) é verdadeiro para um inteiro k ≥ 1
arbitrário. Queremos mostrar que P (k + 1) também será verdadeiro.
Note que em um grupo qualquer de k + 1 pessoas, podemos colocá-as em fila e observar que as k
primeiras formam um grupo de k pessoas. Pela hipótese de indução, essas pessoas têm todas a mesma
cor de olhos. Da mesma forma, na fila de k + 1 pessoas, as k últimas formam também um grupo de
k pessoas e, pela hipótese de indução, têm todas a mesma cor de olhos. Como o grupo de k primeiras
pessoas da fila e o grupo de k últimas têm uma interseção, somos obrigados a concluir que todas as
pessoas da fila têm a mesma cor de olhos.
Solução do professor: O erro da “demonstração” é que o passo indutivo não vale quando k = 1, ou
seja, a implicação P (1)→ P (2) não é necessariamente verdadeira (interessantemente, ela é verdadeira
para todo outro k ≥ 2).
Num grupo de k + 1 = 2 pessoas, a fila das k = 1 primeiras pessoas têm todas a mesma cor de olhos
(por exemplo, castanhos), e a fila das k = 1 últimas pessoas também têm todas a mesma cor de olhos
(por exemplo, verdes). Entretanto, não há interseção entre o grupo de k = 1 primeiras pessoas e o
grupo de k = 1 últimas pessoas da fila, e, portanto, não se pode concluir que as pessoas dos dois
grupos devem ter a mesma cor de olhos.
8