Aula 4-Primeiro Princípio da Indução Matemática

Prévia do material em texto

Primeiro 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 primeiro 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 k ≥ a, então ela necessariamente é
verdadeira para k + 1
Observe que o raciocínio que usamos nesse tipo de demonstração é o de desencadeamento
de verdades.
Exemplo 1. Prove as seguintes afirmações utilizando a técnica de indução matemática.
(a)
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + ...+
1
n(n+ 1)
=
n
n+ 1
para todo n ∈ N.
(b) A soma dos quadrados dos n primeiros números naturais é igual a
n(n+ 1)(2n+ 1)
6
para
todo n ∈ N
(c) 8 divide 32n + 7 para todo n ∈ N.
(d) 12 − 22 + 32 − 42 + ...+ (−1)n−1n2 = (−1)n−1
[
n(n+ 1)
2
]
para todo n ∈ N
(e) Suponha que um rei tem 3n moedas de ouro (n ∈ N) e dessas moedas apenas uma é falsa
e mais leve que as outras. A diferença de peso é quase imperceptível e o único jeito de
determinar se a moeda é falsa é pesando ela em uma balança de dois pratos. Mostre que
com n pesagens o rei consegue descobrir a moeda falsa.
(f) Todo valor de postagem de 20 centavos ou mais pode ser formado utilizando-se apenas selos
de 5 e 6 centavos.
(g) n! > 3n se n é um número natural maior ou igual a 7
Resolução:
(a) A conjectura pode ser escrita como
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + ...+
1
n(n+ 1)
=
n
n+ 1
∀n ∈ N
Hipótese: n ∈ N
Tese:
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + ...+
1
n(n+ 1)
=
n
n+ 1
Utilizando o princípio de indução matemática temos que
(1) O primeiro natural que satisfaz a hipótese é n = 1. Para n = 1, temos que
• 1
1 · 2 =
1
2
• n
n+ 1
=
1
1 + 1
=
1
2
Logo, a tese é verdadeira para n = 1.
1
(2) Suponha que a tese é verdadeira para k ∈ N, isto é, que
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + ...+
1
k(k + 1)
=
k
k + 1
Vamos mostrar (utilizando a tese para k) que a tese também vale para k + 1. Observe
que a tese para n = k + 1 é
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + ...+
1
k(k + 1)
+
1
(k + 1)(k + 2)
=
k + 1
k + 2
e, portanto, é isso que nós queremos provar. Temos que
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + ...+
1
n · (n+ 1) =
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + ...+
1
k · (k + 1) +
1
(k + 1)(k + 2)
=
k
k + 1
+
1
(k + 1)(k + 2)
=
k(k + 2)
(k + 1)(k + 2)
+
1
(k + 1)(k + 2)
=
k(k + 2) + 1
(k + 1)(k + 2)
=
k2 + 2k + 1
(k + 1)(k + 2)
=
(k + 1)2
(k + 1)(k + 2)
=
k + 1
k + 2
=
n
n+ 1
Logo, a tese vale para k + 1
Concluímos que a tese é verdadeira para todo n ∈ N
(b) A conjectura pode ser escrita como
12 + 22 + 32 + ...+ n2 =
n(n+ 1)(2n+ 1)
6
∀n ∈ N
Hipótese: n ∈ N
Tese: 12 + 22 + 32 + ...+ n2 =
n(n+ 1)(2n+ 1)
6
Utilizando o princípio de indução matemática temos que
(1) O primeiro natural que satisfaz a hipótese é n = 1. Para n = 1, temos que
• 12 = 1
2
• n(n+ 1)(2n+ 1)
6
=
1 · 2 · 3
6
=
6
6
= 1
Logo, a tese é verdadeira para n = 1.
(2) Suponha que a tese é verdadeira para k ∈ N, isto é, que
12 + 22 + 32 + ...+ k2 =
k(k + 1)(2k + 1)
6
Vamos mostrar (utilizando a tese para k) que a tese também vale para k + 1. Observe
que a tese para n = k + 1 é
12 + 22 + 32 + ...+ k2 + (k + 1)2 =
(k + 1)(k + 2)(2(k + 1) + 1)
6
e, portanto, é isso que nós queremos provar. Temos que
12 + 22 + 32 + ...+ n2 = 12 + 22 + 32 + ...+ k2 + (k + 1)2
=
k(k + 1)(2k + 1)
6
+ (k + 1)2
=
k(2k2 + 2k + k + 1)
6
+ k2 + 2k + 1
=
k(2k2 + 3k + 1)
6
+
6(k2 + 2k + 1)
6
=
2k3 + 3k2 + k
6
+
6k2 + 12k + 6
6
=
2k3 + 3k2 + k + 6k2 + 12k + 6
6
=
2k3 + 9k2 + 13k + 6
6
Mas temos que para n = k + 1,
n(n+ 1)(2n+ 1)
6
=
(k + 1)(k + 2)(2(k + 1) + 1)
6
=
(k + 1)(k + 2)(2k + 2 + 1)
6
=
(k + 1)(k + 2)(2k + 3)
6
=
(k2 + 2k + k + 2)(2k + 3)
6
=
(k2 + 3k + 2)(2k + 3)
6
=
2k3 + 3k2 + 4k + 6k2 + 9k + 6
6
=
2k3 + 9k2 + 13k + 6
6
3
Logo, se n = k + 1, temos
12 + 22 + 32 + ...+ n2 =
2k3 + 3k2 + 4k + 6k2 + 9k + 6
6
=
n(n+ 1)(2n+ 1)
6
e, portanto, a tese vale para k + 1
Concluímos que a tese é verdadeira para todo n ∈ N
(c) Hipótese: n ∈ N
Tese: 8| (32n + 7)
Utilizando o princípio de indução matemática temos que
(1) O primeiro natural que satisfaz a hipótese é n = 1. Para n = 1, temos que
32n + 7 = 32 + 7 = 9 + 7 = 16
Como 8|16, então a tese é verdadeira para n = 1.
(2) Suponha que a tese é verdadeira para k ∈ N, isto é, que 8| (32k + 7). Vamos mostrar
(utilizando a tese para k) que a tese também vale para k+1. Como 8| (32k + 7), então
existe m ∈ N tal que 32k + 7 = 8m. Se n = k + 1, então
32n + 7 = 32(k+1) + 7 = 32k+2 + 7 = 32k · 32 + 7
= 9 · 32k + 7 = 9 · 32k + 63− 63 + 7
= 9 · 32k + 63 + 56 = 9(32k + 7) + 56 = 9 · 8m+ 56
= 8(9m+ 7)
Como 8|8(9m+ 7) (pois 9m+ 8 ∈ N, então a tese vale para k + 1
Concluímos que a tese é verdadeira para todo n ∈ N
(d) A conjectura pode ser escrita como
12 − 22 + 32 − 42 + ...+ (−1)n−1n2 = (−1)n−1
[
n(n+ 1)
2
]
∀n ∈ N
Hipótese: n ∈ N
Tese: 12 − 22 + 32 − 42 + ...+ (−1)n−1n2 = (−1)n−1n(n+ 1)
2
Utilizando o princípio de indução matemática temos que
(1) O primeiro natural que satisfaz a hipótese é n = 1. Para n = 1, temos que
• 12 = 1
• (−1)n−1
[
n(n+ 1)
2
]
= (−1)0
[
1 · 2
2
]
= 1
[
2
2
]
= 1
Logo, a tese é verdadeira para n = 1.
(2) Suponha que a tese é verdadeira para k ∈ N, isto é, que
12 − 22 + 32 − 42 + ...+ (−1)k−1k2 = (−1)k−1
[
k(k + 1)
2
]
4
Vamos mostrar (utilizando a tese para k) que a tese também vale para k + 1. Observe
que a tese para n = k + 1 é
12 − 22 + 32 − 42 + ...+ (−1)k−1k2 + (−1)k(k + 1)2 = (−1)k
[
(k + 1)(k + 2)
2
]
e, portanto, é isso que nós queremos provar. Temos que
12 − 22 + 32 − 42 + ...+ (−1)n−1n2 = 12 − 22 + 32 − 42 + ...+ (−1)k−1k2 + (−1)k(k + 1)2
= (−1)k−1
[
k(k + 1)
2
]
+ (−1)k(k + 1)2
=
(−1)k
(−1)
[
k(k + 1)
2
]
+ (−1)k(k + 1)2
= (−1)k(−1)
[
k(k + 1)
2
]
+ (−1)k(k2 + 2k + 1)
= (−1)k(−1)k
2 + k
2
+ (−1)k 2(k
2 + 2k + 1)
2
= (−1)k
[
(−1)k
2 + k
2
+
2k2 + 4k + 2
2
]
= (−1)k
[
−k
2 + k
2
+
2k2 + 4k + 2
2
]
= (−1)k
[−k2 − k + 2k2 + 4k + 2
2
]
= (−1)k
[
k2 + 3k + 2
2
]
Mas temos que para n = k + 1,
(−1)n−1
[
n(n+ 1)
2
]
= (−1)k
[
(k + 1)(k + 2)
2
]
= (−1)k
[
k2 + 2k + k + 1
2
]
= (−1)k
[
k2 + 3k + 1
2
]
Logo, se n = k + 1, temos
12 − 22 + 32 − 42 + ...+ (−1)n−1n2 = (−1)k
[
k2 + 3k + 1
2
]
= (−1)n−1
[
n(n+ 1)
2
]
e, portanto, a tese vale para k + 1
5
Concluímos que a tese é verdadeira para todo n ∈ N
(e) Hipótese: O rei possui 3n moedas das quais uma é falsa e mais leve que as verdadeiras.
n ∈ N.
Tese: É possível identificar a moeda falsa com n pesagens em uma balança de dois pratos.
Utilizando o princípio de indução matemática temos que
(1) O primeiro número natural que satisfaz a hipótese é n = 1. Se o rei tiver apenas 3
moedas então ele pode pesar apenas duas dessas moedas e
• Se um lado da balança estiver mais alto que o outro, então a moeda falsa é a que
está no prato mais alto.
• Se os dois lados da balança estiverem iguais, então a moeda falsa é a que não está
sendo pesada.
Logo, podemos identificar entre 3 moedas qual é a falsa utilizando apenas uma pesagem
e, portanto, a tese vale para n = 1.
(2) Suponha que a tese é verdadeira para k (onde k ≥ 1), ou seja, que podemos determinar
entre 3k moedas qual é a moeda falsa utilizando k pesagens. Vamos mostrar que a tese
também vale para k + 1, ouseja, que podemos determinar utilizando k + 1 pesagens
qual entre 3k+1 moedas é a falsa. Se tivermos 3k+1 = 3 · 3k moedas, podemos
• Separar essas moedas em 3 grupos de 3k moedas cada.
• Pesar dois dos grupos de 3k moedas para identificar em qual grupo está a moeda
falsa. Para tanto, observamos que se um lado da balança estiver mais alto que o
outro, então a moeda falsa está no grupo do prato mais alto e se os dois lados da
balança estiverem iguais, então a moeda falsa está no grupo que não está sendo
pesado.
• Utilizar k pesagens no grupo de 3k moedas que contém a moeda falsa para deter-
minar qual é a moeda falsa.
Logo, utilizando k + 1 pesagens conseguimos determinar qual entre 3k+1 moedas é a
falsa.
Concluímos que a tese é verdadeira para todo n ∈ N.
(f) Hipótese: A postagem custa n centavos, onde n ∈ N, n ≥ 20
Tese: A postagem pode ser feita utilizando apenas selos de 5 centavos e de 6 centavos.
Utilizando o princípio de indução matemática temos que
(1) O primeiro número natural que satisfaz a hipótese é n = 20. Como uma postagem de
20 centavos pode ser feito utilizando 4 selos de 5 centavos, então a tese é verdadeira
para n = 20.
(2) Suponha que a tese é verdadeira para k (onde k ≥ 20), ou seja, que uma postagem de
k centavos pode ser feita utilizando apenas selos de 5 centavos e de 6 centavos. Vamos
mostrar que a tese também vale para k + 1, ou seja, vale se a postagem custar k + 1
centavos. Observe que
• Se dentre os selos que geram os k centavos existir pelo menos um selo de 5 centavos,
então basta substituir esse selo por um de 6 centavos para obter os k+1 centavos.
6
• Se dentre os selos que geram os k centavos não existir nenhum selo de 5 centavos,
então isto quer dizer que k é obtido utilizando uma quantidade m de selos de 6
centavos apenas e m ≥ 4 (pois k ≥ 20). Logo, os k+1 centavos podem ser obtidos
substituindo 4 dos selos de 6 centavos de k por 5 selos de 5 centavos, pois
6(m− 4) + 5 · 5 = 6m− 24 + 25 = 6m+ 1 = k + 1
Logo, a tese é válida para k + 1.
Concluímos que a tese é verdadeira para todo n ∈ N, n ≥ 20.
(g) Hipótese: n ∈ N, n ≥ 7
Tese: n! > 3n
Utilizando o princípio de indução matemática temos que
(1) O primeiro natural que satisfaz a hipótese é n = 7. Para n = 7, temos que
• 3n = 37 = 2187
• n! = 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040
Como 7! = 5040 > 2187 = 37, então a tese é verdadeira para n = 7.
(2) Suponha que a tese é verdadeira para k ≥ 7, isto é, que k! > 3k. Vamos mostrar
(utilizando a tese para k) que a tese também vale para k + 1. Como k + 1 > 7 > 3,
então se n+ k + 1, temos
n! = (k + 1)! = (k + 1) · k! > (k + 1) · 3k > 3 · 3k = 3k+1
Logo, a tese vale para k + 1
Concluímos que a tese é verdadeira para todo n ∈ N
7