Indução Matemática

Prévia do material em texto

Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Induc¸a˜o Matema´tica
Renata de Freitas e Petrucio Viana
Instituto de Matema´tica e Estat´ıstica, UFF
Setembro de 2013
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Suma´rio
• A estrutura dos naturais.
• O me´todo de induc¸a˜o matema´tica.
• Induc¸a˜o forte.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Augustus De Morgan
Augustus De Morgan
(1806 – 1871)
• Definiu induc¸a˜o matema´tica,
me´todo ate´ enta˜o usado sem
clareza e com pouco rigor.
• Foi um pioneiro no estudo da
a´lgebra de relac¸o˜es.
• Preparou o surgimento da
lo´gica formal.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Exemplo
Dados
A = N∗
e
B =
{
n ∈ N∗ : 1 + 2 + · · ·+ n = n(n + 1)
2
}
,
temos A ⊆ B?
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Prova:
Seja n ∈ N∗.
??????????
Por que 1 + 2 + · · ·+ n = n(n + 1)
2
???
??????????
Logo, n ∈ B.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Prova (atribu´ıda a Gauss, ± 1780):
Seja n ∈ N∗.
Temos que:
1 + 2 + 3 + · · · + (n − 1) + n
n + (n − 1) + (n − 2) + · · · + 2 + 1
(n + 1) + (n + 1) + (n + 1) + · · · + (n + 1) + (n + 1)
Assim, 2(1 + 2 + · · ·+ n) = n(n + 1).
E, portanto, 1 + 2 + · · ·+ n = n(n + 1)
2
.
Logo, n ∈ B.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
A estrutura de N
O conjunto N possui uma certa estrutura.
Os naturais sa˜o formados a partir de 0, por aplicac¸o˜es
sucessivas da operac¸a˜o +1.
0 1 2 3 · · · n n+1 · · ·
+1
��
+1
��
+1
��
+1
��
Esta estrutura nos leva a um novo me´todo para a prova de
incluso˜es N ⊆ A.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
O me´todo de induc¸a˜o matema´tica
Se queremos provar que
N ⊆ A, ou que ∀x(x ∈ N→ P(x)),
onde P(x) e´ a propriedade que define A, basta fazer o seguinte:
(B) Mostrar que P(x) vale para o primeiro nu´mero natural:
P(0)
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
O me´todo de induc¸a˜o matema´tica
- Mostrar que, se um determinado nu´mero natural possui a
propriedade P(x), enta˜o o nu´mero natural seguinte
tambe´m possui a propriedade P(x):
P(n)→ P(n + 1)
Ou seja,
(H) Supor que P(n), para um determinado nu´mero natural n.
(P) Mostrar que P(n + 1), usando o fato de que P(n).
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Provando generalizac¸o˜es
∀x(x ∈ N→ P(x))
Dada uma propriedade P(x), a prova de que
∀x(x ∈ N→ P(x)) pelo me´todo de induc¸a˜o matema´tica deve
seguir o seguinte modelo de redac¸a˜o:
1. Escreva “Prova (por induc¸a˜o em x):” ao iniciar a prova;
2. Escreva “Base:”;
3. Explique, ta˜o detalhadamente quanto voceˆ achar
necessa´rio, por que P(0);
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Provando generalizac¸o˜es
∀x(x ∈ N→ P(x))
4. Escreva “Hipo´tese: Seja x tal que P(x)” ou qualquer
sentenc¸a contendo a mesma informac¸a˜o;
5. Escreva “Passo:”;
6. Explique, ta˜o detalhadamente quanto voceˆ achar
necessa´rio, por que P(x + 1) e´ verdadeira;
7. Escreva “Logo, x e´ tal que P(x + 1)” ou qualquer frase
contendo a mesma informac¸a˜o;
8. Escreva “ ” para terminar a prova.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Provando generalizac¸o˜es
∀x(x ∈ N→ P(x))
Prove que para todos os naturais x , temos que
30 + 31 + 32 + · · ·+ 3x = 3
x+1 − 1
2
,
ou seja,
∀x
(
x ∈ N → 30 + 31 + 32 + · · ·+ 3x = 3
x+1 − 1
2
)
,
usando o me´todo de induc¸a˜o matema´tica.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Neste exemplo, temos que
P(x) : 30 + 31 + 32 + · · ·+ 3x = 3
x+1 − 1
2
P(0) : 30 =
30+1 − 1
2
P(x + 1) : 30 + 31 + 32 + · · ·+ 3x + 3x+1 = 3
(x+1)+1 − 1
2
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Prova (por induc¸a˜o em x):
Base:
Temos que 30 = 1.
Ale´m disso,
30+1 − 1
2
=
3− 1
2
=
2
2
= 1.
Logo, 30 =
30+1 − 1
2
.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Hipo´tese:
Suponhamos que x e´ tal que
30 + 31 + 32 + · · ·+ 3x = 3
x+1 − 1
2
.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Passo:
Pela hipo´tese de induc¸a˜o, temos que
30 + 31 + 32 + · · ·+ 3x + 3x+1 = 3
x+1 − 1
2
+ 3x+1
=
3x+1 − 1 + 2 · 3x+1
2
=
3 · 3x+1 − 1
2
=
3(x+1)+1 − 1
2
.
Logo, x e´ tal que
30 + 31 + 32 + · · ·+ 3x + 3x+1 = 3
(x+1)+1 − 1
2
.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
A estrutura de N
• Dado a ∈ N, o conjunto {x ∈ N : x ≥ a} possui uma
estrutura ana´loga a de N.
• Os naturais maiores ou iguais a um certo valor a sa˜o
formados a partir de a, por aplicac¸o˜es sucessivas da
operac¸a˜o +1.
a (a+1) (a+2) · · · (a+n) (a+n+1) · · ·
+1
��
+1
��
+1
��
• Esta analogia nos permite utilizar o me´todo de induc¸a˜o
matema´tica para a prova de generalizac¸o˜es
∀x ∈ N(x ≥ a→ P(x)).
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
O me´todo de induc¸a˜o matema´tica
Se queremos provar que
para todo natural maior ou igual a a temos que P(x),
basta fazer o seguinte:
(B) Mostrar que a possui a propriedade P(x):
P(a)
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
O me´todo de induc¸a˜o matema´tica
- Mostrar que, se um determinado nu´mero natural n maior
ou igual a a possui a propriedade P(x), enta˜o o nu´mero
natural seguinte tambe´m possui a propriedade P(x):
P(n)→ P(n + 1)
Ou seja,
(H) Supor que P(n), para um determinado nu´mero natural n
tal que n ≥ a.
(P) Mostrar que P(n + 1), usando o fato de que P(n).
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Problema 1
Prove que
∀x
(
x ∈ N∗ → 1 + 2 + · · ·+ x = x(x + 1)
2
)
,
usando o me´todo de induc¸a˜o matema´tica.
Induc¸a˜o
Matema´ticaRenata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
O me´todo de induc¸a˜o matema´tica
O me´todo de induc¸a˜o pode ser formulado de outra maneira,
chamada de:
Induc¸a˜o forte
Se queremos provar que
para todo natural maior ou igual a a temos que P(x),
basta fazer o seguinte:
(B) Mostrar que a possui a propriedade P(x):
P(a)
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
O me´todo de induc¸a˜o matema´tica
- Mostrar que, se todos os naturais k tais que a ≤ k ≤ n
possuem a propriedade P(x), enta˜o n + 1 tambe´m possui
a propriedade P(x):
∀k(a ≤ k ≤ n → P(k)) → P(n + 1)
Ou seja,
(H) Supor que ∀k(a ≤ k ≤ n → P(k)).
(P) Mostrar que P(n + 1), usando o fato de que
∀k(a ≤ k ≤ n → P(k)).
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Problema 2
Prove que todo nu´mero natural maior ou igual a 2 pode ser
escrito como produto de nu´meros primos.
Induc¸a˜o
Matema´tica
Renata de
Freitas e
Petrucio
Viana
A estrutura
dos naturais
O me´todo de
induc¸a˜o
matema´tica
Induc¸a˜o forte
Exerc´ıcios
1. Exerc´ıcios do Cap´ıtulo 8 do Menezes
(Paulo B. Menezes, Matema´tica Discreta para Computac¸a˜o e
Informa´tica, 2a. edic¸a˜o, Sagra Luzzatto / Instituto de Informa´tica da
UFRGS, Porto Alegre, 2006).
2. Exerc´ıcios do Cap´ıtulo 4 do Scheinerman
(E.R. Scheinerman, Matema´tica Discreta, Thomson, Sa˜o Paulo,
2006).
3. Exerc´ıcios da Lista 3.
	A estrutura dos naturais
	O método de indução matemática
	Indução forte