TEORIA DOS NÚMEROS
Aula 2 – Princípio da Indução Finita
Prof. Mário Alves
TEORIA DOS NÚMEROS
Conteúdo Programático desta aula
 Princípio da Boa Ordenação;
 Princípio da Indução Finita; e
 Exemplos.
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
PRINCÍPIO DA BOA ORDENAÇÃO
Vamos a algumas definições para que
compreender melhor o conteúdo de nossa aula:
possamos
Definição: Seja A um conjunto de inteiros. Denominamos
elemento mínimo de A um elemento a pertencente a A tal
que a é menor ou igual a x, para todo x pertencente a A.
min A = a ⇔ (a ∈ A e (∀x ∈ A)(a ≤ x)
Teorema Nr 2.1: Se a é elemento mínimo de A, então este
elemento é único.
O elemento mínimo de A, se existe, chamamos de menor
elemento de A ou primeiro elemento de A.
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
PRINCÍPIO DA BOA ORDENAÇÃO
- Exemplo Nr 2.1: O conjunto N = {1,2,3,4,5,...} dos inteiros
positivos possui o 1 como elemento mínimo (mín N=1), pois
1 pertence a N e 1 é menor ou igual a n, para qualquer n
pertencente a N.
- Exemplo Nr 2.2: O conjunto A = { x ∈ z | x > 8} tem o
elemento mínimo 9 (min A=9), pois 9 pertence a A e 9 é
menor ou igual a x, para todo x pertencente a A.
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
PRINCÍPIO DA BOA ORDENAÇÃO
- Exemplo Nr 2.3: O conjunto Z- = {0, -1, -2, -3, -4, ...} dos
números inteiros não positivos não tem elemento mínimo,
já que não existe a pertencente ao conjunto tal que a seja
menor ou igual a x, para todo x pertencente a Z- .
2
- Exemplo Nr 2.4: O conjunto J = {x ∈ N| 3 divide x } tem
o elemento mínimo 3 (mín J = 3), pois 3 pertence a J (3
divide 9) e 3 ≤ x para todo x ∈ J ( 1∈ A e 2 ∈ A)
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
PRINCÍPIO DA INDUÇÃO FINITA
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
PRINCÍPIO DA INDUÇÃO FINITA
Teorema Nr 2.2: Seja P(n) uma proposição associada a cada
inteiro positivo n e que satisfaça às seguintes condições:
(1) P(1) é verdadeira;
(2) Para todo inteiro positivo k, se P(k) é verdadeira, então
P(k+1) também é verdadeira.
-
Assim, a proposição P(n) é verdadeira para todo inteiro
positivo n.
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
EXEMPLOS E EXERCÍCIOS
Exercício Nr 2.1: Mostre que:
P(n): 1+3+5+7+...+(2n-1) = n2, ∀ n ∈ N
Solução:
- P(1) é verdadeira, pois 1 = 12.
- A hipótese de indução é que a proposição:
P(k): 1+3+5+...+(2k-1) = k2, k ∈N é verdadeira.
- Adicionando 2k+1 a ambos os membros da igualdade,
obtemos:
1+3+5+...+(2k-1)+(2k+1) = k2 + (2k+1) = (k+1)2,
o que mostra que P(k+1) é verdadeira.
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
EXEMPLOS E EXERCÍCIOS
Exercício Nr 2.2: Demonstre a proposição abaixo:
1
1
1
1
n
P(n) =
+
+
+ ... +
=
,∀ n ∈N
1.2 2.3 3.4
n(n + 1) n + 1
Solução:
1
1
- P(1) é verdade, pois
=
1.2 1 + 1
-
Nossa hipótese de indução é:
1
1
1
1
k
P(k) =
+
+
+ ... +
=
, k ∈N
1.2 2.3 3.4
k(k + 1) k + 1
é verdadeira
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
EXEMPLOS E EXERCÍCIOS
-
Somando
teremos:
1
(k + 1).(k + 2) a
ambos os lados da equação anterior,
1
1
1
1
1
k
1
+
+
+ ... +
+
=
+
=
1.2 2.3 3.4
k(k + 1) (k + 1)(k + 2) k + 1 (k + 1)(k + 2)
k 2 + 2k + 1
k +1
=
=
(k + 1)(k + 2) k + 2
-
Ou seja, significa que a proposição P(k+1) é verdadeira.
Assim, P(n) é verdade para todo inteiro positivo n.
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
EXEMPLOS E EXERCÍCIOS
Exercício Nr 2.3: Demonstre que:
P(n): 3|(22n-1), ∀ n ∈ N
Solução:
- P(1) é verdadeira, pois 3|(22.1-1)
- A hipótese de indução é que a proposição:
P(k): 3|(22k-1), k∈N é verdadeira. Portanto:
22k-1 = 3q, com q ∈Z;
- Assim:
22(k+1)-1 = 22.22k -1 = 4. 22k – 1= 4. 22k – 4 + 4 – 1 =
= 4(22k – 1) +3 = 4.3q + 3 = 3(4q+1)
- Logo, a proposição P(k+1) é verdadeira. Assim, P(n) é
verdadeira para todo inteiro positivo n.
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
EXEMPLOS E EXERCÍCIOS
Exercício Nr 2.4: Prove que a seguinte afirmação A(n) é
verdadeira para todo n pertencente a Z com n maior ou
igual a 1:
A(n): A soma dos primeiros n números inteiros positivos é
dada por:
1+2+3+4+5+...+n = n.(n-1)/2.
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2
TEORIA DOS NÚMEROS
EXEMPLOS E EXERCÍCIOS
Solução:
- P(1) é verdadeira, pois 1(1+1)/2 = 2/2 = 1.
-
-
A hipótese de indução é que a proposição:
P(k): 1+2+3+4+5+...+k = k(k+1)/2, k ∈N é verdadeira.
Adicionando k+1 a ambos os membros da igualdade,
obtemos:
1+2+3+4+5+...+k +(k+1) = k(k+1)/2 + (k+1) =
= (k+1)(k/2 + 1) = (k+1)(k+2)/2,
o que mostra que P(k+1) é verdadeira, e P(n) é verdadeira
para todo n∈Z com n ≥1.
PRINCÍPIO DA INDUÇÃO FINITA– AULA 2