Aula 5-Segundo Princípio da Indução Matemática

Prévia do material em texto

Segundo Princípio da Indução Matemática
Suponha que queremos mostrar que uma certa conjectura vale para todos os valores de
n ∈ N, n ≥ a. Para demonstrar essa conjectura pelo segundo princípio de indução matemática,
basta mostrar que
(1) A conjectura vale para n = a.
(2) Se assumirmos que a conjectura é verdadeira para todo n tal que a ≤ n ≤ k, então ela
necessariamente é verdadeira para k + 1.
A diferença entre o primeiro princício de indução e o segundo é que na segunda parte do
primeiro princício assumimos que a tese é válida para k e utilizamos isso para mostrar que a
tese é válida para k+1, enquanto na segunda parte do segundo princípio de indução, assumimos
que a tese é válida para todo n ≤ k satisfazendo a hipótese e utilizamos essas teses para mostrar
que a tese vale para k + 1.
Em outras palavras, se q(n) é a tese a ser provada para n ∈ N, n ≥ a, então:
• No primeiro princípio de indução temos que mostrar que
(1) q(a) é verdadeira.
(2) se k ≥ a e se q(k) é verdadeira, então q(k + 1) é verdadeira.
• No segundo princípio de indução temos que mostrar que
(1) q(a) é verdadeira.
(2) se q(n) é verdadeira para todo n tal que a ≤ n ≤ k, então q(k + 1) é verdadeira.
Muitas vezes o Primeiro Princípio de Indução Matemática é chamado de Princípio da In-
dução Fraca e o Segundo Princípio de Indução Matemática é chamado de Princípio da Indução
Forte (por ser necessário usar as teses de mais números do que só a tese do número exatamente
anterior ao k + 1, que é o k).
Para demonstar os próximos exemplos precisamos da seguinte definição:
Definição 1. Dizemos que um número n ∈ Z é primo se n possuir exatamente quatro divisores
distintos: 1,−1, n e −n.
Definição 2. Dizemos que um número n ∈ N é primo se n possuir exatamente dois divisores
positivos distintos: 1 e n.
Exemplo 1. Prove as seguintes afirmações utilizando a técnica de indução matemática.
(a) Todo número natural maior ou igual a 2 pode ser fatorado em números naturais primos (ou
seja, todo número natural maior ou igual a 2 é primo ou pode ser escrito como o produto
de números naturais primos).
(b) Todo valor de postagem de 20 centavos ou mais pode ser formado utilizando-se apenas selos
de 5 e 6 centavos.
(c) Todo valor de postagem de 18 centavos ou mais pode ser formado utilizando-se apenas selos
de 4 e 7 centavos.
(d) A sequência 1, 1, 2, 3, 5, 8, 13, ... é chamada de sequência de Fibonacci. Se denotarmos o
n-ésimo termo da sequência por Fn, então os termos da sequência seguem a regra:
1
• F1 = 1
• F2 = 1
• Fn = Fn−1 + Fn−2 se n ≥ 3
Mostre que Fn <
(
7
4
)n
para todo n ∈ N.
(e) Considere a sequência cujo n-ésimo termo an é dado por
• a1 = 1
• a2 = 2
• an = 4an−1 − 4an−2 se n ≥ 3
Mostre que an = 2
n−1
para todo n ∈ N.
(f) Considere a sequência cujo n-ésimo termo an é dado por
• a1 = 1
• a2 = 2
• a3 = 3
• an = an−1 + an−2 + an−3 se n ≥ 4
Mostre que an < 3
n
para todo n ∈ N.
Resolução:
(a) A conjectura pode ser escrita como
(n ∈ N, n ≥ 2) → n pode ser fatorado em números naturais primos
Hipótese: n ∈ N, n ≥ 2
Tese: n pode ser fatorado em números naturais primos
Utilizando o segundo princípio de indução matemática temos que
(1) O primeiro natural que satisfaz a hipótese é n = 2. Como 2 é primo, então ele em si
já é uma fatoração em números primos. Logo, a tese é verdadeira para n = 2.
(2) Suponha que a tese é verdadeira para todo n ∈ N tal que 2 ≤ n ≤ k, ou seja, que todo
número natural entre 2 e k pode ser fatorado em números primos positivos. Vamos
mostrar (utilizando a tese para esses valores de n) que a tese também vale para k + 1.
Temos que:
• Se k + 1 for primo, então ele em si já é uma fatoração em números primos.
• Se k + 1 não for primo, então k + 1 possui algum divisor natural a diferente de 1
e de k + 1. Ou seja,
∃ a ∈ N / (a 6= 1, a 6= k + 1 e a|(k + 1))
Logo, ∃ b ∈ N / k + 1 = ab. Mas, como 2 ≤ a ≤ k + 1 e 2 ≤ b ≤ k + 1, então
a e b podem ser fatorados em números naturais primos e o produto dessas duas
fatorações é uma fatoração para k + 1.
Concluímos que a tese é verdadeira para todo n ∈ N, n ≥ 2.
2
(b) A conjectura pode ser escrita como
(n ∈ N, n ≥ 20) → (∃ m, c ∈ (N ∪ {0}) / n = 5m+ 6c)
Hipótese: n ∈ N, n ≥ 20
Tese: ∃ m, c ∈ (N ∪ {0}) / n = 5m+ 6c
Utilizando o segundo princípio de indução matemática temos que
(1) O primeiro natural que satisfaz a hipótese é n = 20. Como 20 = 5 · 4 + 6 · 0, então 20
pode ser escrito como uma soma de múltiplos não-negativos de 5 e de 6. Logo, a tese
é verdadeira para n = 20.
(2) Suponha que a tese é verdadeira para todo n ∈ N tal que 20 ≤ n ≤ k, ou seja, que
todo número natural entre 20 e k pode ser escrito como uma soma de múltiplos não-
negativos de 5 e de 6. Vamos mostrar que a tese também vale para k + 1. Observe
que
k + 1 = (k − 4) + 5
Logo, se a tese for verdadeira para k− 4, então ela será verdadeira para k+1, uma vez
que teremos k − 4 = 5m+ 6c para algum m, c ∈ (N ∪ {0}) e, portanto,
k + 1 = (k − 4) + 5 = 5m+ 6c+ 5 = 5 (m+ 1)︸ ︷︷ ︸
∈N
+6c
Entretanto temos que tomar cuidado, pois estamos assumindo que a tese é válida para
os valores de n ∈ N tais que 20 ≤ n ≤ k e
k − 4 ≥ 20 ↔ k ≥ 24
Logo, se k + 1 ≥ 25, então a tese é válida para k − 4 e, portanto, é válida para k + 1.
Nos resta mostrar então apenas que a tese vale para n = 21, n = 22, n = 23 e n = 24.
Temos que
• 21 = 5 · 3 + 6 · 1 e, portanto, a tese vale para n = 21
• 22 = 5 · 2 + 6 · 2 e, portanto, a tese vale para n = 22
• 23 = 5 · 1 + 6 · 3 e, portanto, a tese vale para n = 23
• 24 = 5 · 0 + 6 · 4 e, portanto, a tese vale para n = 24
Concluímos que a tese é verdadeira para todo n ∈ N, n ≥ 20.
(c) A conjectura pode ser escrita como
(n ∈ N, n ≥ 18) → (∃ m, c ∈ (N ∪ {0}) / n = 4m+ 7c)
Hipótese: n ∈ N, n ≥ 18
Tese: ∃ m, c ∈ (N ∪ {0}) / n = 4m+ 7c
Utilizando o segundo princípio de indução matemática temos que
(1) O primeiro natural que satisfaz a hipótese é n = 18. Como 18 = 1 · 4 + 2 · 7, então 18
pode ser escrito como uma soma de múltiplos não-negativos de 4 e de 7. Logo, a tese
é verdadeira para n = 18.
3
(2) Suponha que a tese é verdadeira para todo n ∈ N tal que 18 ≤ n ≤ k, ou seja, que
todo número natural entre 18 e k pode ser escrito como uma soma de múltiplos não-
negativos de 5 e de 6. Vamos mostrar que a tese também vale para k + 1. Observe
que
k + 1 = (k − 3) + 4
Logo, se a tese for verdadeira para k− 3, então ela será verdadeira para k+1, uma vez
que teremos k − 3 = 4m+ 7c para algum m, c ∈ (N ∪ {0}) e, portanto,
k + 1 = (k − 3) + 4 = 4m+ 7c+ 4 = 4 (m+ 1)︸ ︷︷ ︸
∈N
+7c
Entretanto temos que tomar cuidado, pois estamos assumindo que a tese é válida para
os valores de n ∈ N tais que 18 ≤ n ≤ k e
k − 3 ≥ 18 ↔ k ≥ 21
Logo, se k + 1 ≥ 22, então a tese é válida para k − 3 e, portanto, é válida para k + 1.
Nos resta mostrar então apenas que a tese vale para n = 19, n = 20 e n = 21. Temos
que
• 19 = 4 · 3 + 7 · 1 e, portanto, a tese vale para n = 19
• 20 = 4 · 5 + 7 · 0 e, portanto, a tese vale para n = 20
• 21 = 4 · 0 + 7 · 3 e, portanto, a tese vale para n = 21
Concluímos que a tese é verdadeira para todo n ∈ N, n ≥ 18.
(d) Hipótese: n ∈ N
Tese: Fn <
(
7
4
)n
Observe que para n = 1 e n = 2 a tese é verdadeira, pois
F1 = 1 <
7
4
e F2 = 1 <
49
16
Vamos utilizar o segundo princípio de indução matemática para mostrar que a tese vale
para n ≥ 3.
(1) O primeiro natural que satisfaz a hipótese na qual estamos utilizando indução é n = 3.
Temos que
F3 = F2 + F1 = 1 + 1 = 2 =
128
64
<
343
64
=
(
7
4
)3
Logo, a tese é verdadeira para n = 3.
(2) Suponha que a tese é verdadeira para todo n ∈ N tal que 3 ≤ n ≤ k, isto é, que
Fn <
(
7
4
)n
para 3 ≤ n ≤ k. Vamos mostrar que a tese também vale para k + 1. Observe que
k−1 ≥ 2 e, portanto, a tese vale para k−1, uma vez que já mostramos o resultado para
4n = 2 e estamos assumindo que o resultado vale para n se 3 ≤ n ≤ k (e 2 ≤ k−1 < k).
Logo,
Fk+1 = Fk + Fk−1 <
(
7
4
)k
+
(
7
4
)k−1
=
(
7
4
)k
+
(
7
4
)k
7
4
=
(
7
4
)k
+
(
7
4
)k
· 4
7
=
(
7
4
)k [
1 +
4
7
]
=
(
7
4
)k [
11
7
]
<
(
7
4
)k [
7
4
]
=
(
7
4
)k+1
Logo, a tese é verdadeira para k + 1.
Concluímos que a tese é verdadeira para todo n ∈ N.
(e) Hipótese: n ∈ N
Tese: an = 2
n−1
Observe que para n = 1 e n = 2 a tese é verdadeira, pois
a1 = 1 = 2
0 e a2 = 2 = 2
1
Vamos utilizar o segundo princípio de indução matemática para mostrar que a tese vale
para n ≥ 3.
(1) O primeiro natural que satisfaz a hipótese na qual estamos utilizando indução é n = 3.
Temos que
a3 = 4a2 − 4a1 = 8− 4 = 4 = 22
Logo, a tese é verdadeira para n = 3.
(2) Suponha que a tese é verdadeira para todo n ∈ N tal que 3 ≤ n ≤ k, isto é, que
4an−1 − 4an−2 = 2n−1
para 3 ≤ n ≤ k. Vamos mostrar que a tese também vale para k + 1. Observe que
k − 1 > k − 2 ≥ 2 e, portanto, a tese vale para k − 1 e para k − 2, uma vez que já
mostramos o resultado para n = 1, n = 2 e estamos assumindo que o resultado vale
para n se 3 ≤ n ≤ k (e 1 ≤ k − 2 < k − 1 < k). Logo,
ak+1 = 4ak − 4ak−1 = 4 · 2k−1 − 4 · 2k−2
= 22 · 2k−1 − 22 · 2k−2 = 2k+1 − 2k
= 2 · 2k − 2k = 2k
Logo, a tese é verdadeira para k + 1.
Concluímos que a tese é verdadeira para todo n ∈ N.
5
(f) Hipótese: n ∈ N
Tese: an < 3
n
Observe que para n = 1, n = 2 e n = 3 a tese é verdadeira, pois
a1 = 1 < 3
1 a2 = 2 < 3
2 a3 = 3 < 3
3
Vamos utilizar o segundo princípio de indução matemática para mostrar que a tese vale
para n ≥ 4.
(1) O primeiro natural que satisfaz a hipótese na qual estamos utilizando indução é n = 4.
Temos que
a4 = a3 + a2 + a1 = 3 + 2 + 1 = 6 < 3
4
Logo, a tese é verdadeira para n = 4.
(2) Suponha que a tese é verdadeira para todo n ∈ N tal que 4 ≤ n ≤ k, isto é, que
an < 3
n
para 4 ≤ n ≤ k. Vamos mostrar que a tese também vale para k + 1. Observe que
k − 1 > k − 2 > k − 3 ≥ 1 e, portanto, a tese vale para k − 1, para k − 2 e para k − 3,
uma vez que já mostramos o resultado para n = 1, n = 2, n = 3 e estamos assumindo
que o resultado vale para n se 4 ≤ n ≤ k (e 1 ≤ k − 3 < k − 2 < k − 1 < k). Logo,
ak+1 = ak + ak−1 + ak−2 < 3k−1 + 3k−2 + 3k−3
= 32 · 3k−3 + 3 · 3k−3 + 3k−3
= (32 + 3 + 1)3k−3 = 13 · 3k−3
< 27 · 3k−3 = 33 · 3k−3 = 3k
Logo, a tese é verdadeira para k + 1.
Concluímos que a tese é verdadeira para todo n ∈ N.
Exercício 1. Mostre que todo valor de postagem de 12 centavos ou mais pode ser formado
utilizando-se apenas selos de 3 e 4 centavos.
Exercício 2. Considere a sequência cujo n-ésimo termo an é dado por
• a1 = 12
• a2 = 29
• an = 5an−1 − 6an−2 se n ≥ 3
Mostre que an = 5 · 3n−1 + 7 · 2n−1 para todo n ∈ N.
6