indução

Prévia do material em texto

Matemática Discreta
Introdução a Indução Matemática
Erika Coelho
erikamorais@inf.ufg.br
Instituto de Informática
Universidade Federal de Goiás
Indução Matemática
Princípio da Indução Matemática
Para mostrar que P(n) é verdadeira para todos os números inteiros
positivos n, em que P(n) é uma função proposicional, completamos
dois passos:
PASSO BASE: Verificamos que P(1) é verdadeira.
PASSO DE INDUÇÃO: Mostramos que a proposição
condicional P(k)→ P(k + 1) é verdadeira para todos os
números inteiros positivos k .
Indução Matemática
Exemplo 1
Mostre que se n for um inteiro positivo, então
1+ 2+ · · · + n =
n(n + 1)
2
.
Prova:
Considere P(n) como a proposição que afirma que a soma dos
primeiros n números inteiros positivos é n(n + 1)/2.
PASSO BASE: P(1) é verdadeira, pois
1 =
1(1+ 1)
2
.
Indução Matemática
Exemplo 1
Mostre que se n for um inteiro positivo, então
1+ 2+ · · · + n =
n(n + 1)
2
.
Prova:
PASSO DE INDUÇÃO: Assuma que P(k) é verdadeira para
k ∈ Z arbitrário, isto é,
1+ 2+ · · · + k =
k(k + 1)
2
.
Adicionando k + 1 nos dois lados da equação em P(k)
obtemos que:
1+ 2+ · · ·+ k + (k + 1) =
k(k + 1)
2
+ (k + 1),
Indução Matemática
Exemplo 1
Mostre que se n for um inteiro positivo, então
1+ 2+ · · · + n =
n(n + 1)
2
.
Prova:
=
k(k + 1) + 2(k + 1)
2
=
(k + 1)(k + 2)
2
.
O que implica que P(k + 1) é verdadeira. E isto completa o passo
de indução.
Indução Matemática
Exemplo 2
Mostre que se n for um inteiro positivo, então
1+ 3+ 5+ · · · + (2n − 1) = n2.
Prova:
Considere P(n) como a proposição que afirma que a soma dos
primeiros n números inteiros positivos e ímpares é n2.
PASSO BASE: P(1) é verdadeira, pois
1 = 12.
PASSO DE INDUÇÃO: Assuma que P(k) é verdadeira, ou
seja,
1+ 3+ 5+ · · ·+ (2k − 1) = k2.
Indução Matemática
Exemplo 2
Mostre que se n for um inteiro positivo, então
1+ 3+ 5+ · · · + (2n − 1) = n2.
Prova:
Queremos verificar que P(k + 1) é verdadeira, ou seja, que
1+ 3+ 5+ · · · + (2k − 1) + (2k + 1) = (k + 1)2.
Indução Matemática
Exemplo 2
Mostre que se n for um inteiro positivo, então
1+ 3+ 5+ · · · + (2n − 1) = n2.
Prova:
Assumindo que P(k) é verdadeira temos que,
1+ 3+ 5+ · · ·+ (2k − 1) + (2k + 1) = k2 + (2k + 1)
= k2 + 2k + 1 = (k + 1)2.
Logo P(k + 1) é verdadeira, finalizando o passo de indução.
Indução Matemática
Exemplo 3
Mostre que se n for um inteiro não negativo, então
1+ 2+ 22 + · · · + 2n = 2n+1 − 1
Prova:
Considere P(n) como a proposição de que
1+ 2+ 22 + · · · + 2n = 2n+1 − 1 para o número inteiro n.
PASSO BASE: P(0) é verdadeira, pois
20 = 1 = 21 − 1.
PASSO DE INDUÇÃO: Assuma que P(k) é verdadeira, ou
seja, que
1+ 2+ 22 + · · ·+ 2k = 2k+1 − 1
Indução Matemática
Exemplo 3
Mostre que se n for um inteiro não negativo, então
1+ 2+ 22 + · · · + 2n = 2n+1 − 1
Prova:
Observe que, utilizando que P(k) é verdadeira, temos que:
1+ 2+ 22 + · · · + 2k + 2k+1 = (2k+1 − 1) + 2k+1
= 2× 2k+1 − 1 = 2k+2 − 1.
Indução Matemática
Exercício
Prove que seguinte proposição é verdadeira:
n∑
i=1
(2i + 3) = n(n + 4), para todo n ≥ 1.
Indução Matemática
Exemplo 4
Seja n um número natural. Então 3 divide 4n − 1.
Prova:
Considere P(n) como a proposição de que 3|4n − 1 para o número
natural n.
PASSO BASE: P(0) é verdadeira, pois 40 − 1 = 1− 1 = 0 e
3|0.
PASSO DE INDUÇÃO: Assuma que P(k) é verdadeira, ou
seja, que 3|4k − 1
Indução Matemática
Exemplo 4
Seja n um número natural. Então 3 divide 4n − 1.
Prova:
Queremos verificar que 3|4k+1 − 1. Note que
4k+1 − 1 = 4× 4k − 1 = 4× 4k − 4+ 3 = 4(4k − 1) + 3.
Como 3 divide 4k − 1 e 3, consequentemente 3 divide 4k+1 − 1.
Desse modo P(k + 1) é verdadeira.
Indução Matemática
Exemplo 5
Seja n um número inteiro positivo. Então 3 divide n3 − n.
Prova:
Considere P(n) como a proposição de que 3|n3 − n para o número
inteiro positivo n.
PASSO BASE: P(1) é verdadeira, pois 11 − 1 = 1− 1 = 0 e
3|0.
PASSO DE INDUÇÃO: Assuma que P(k) é verdadeira, ou
seja, que 3|k3 − k
Indução Matemática
Exemplo 5
Seja n um número inteiro positivo. Então n3 − n é divisível por 3.
Prova:
Como 3|k3 − k , então existe um inteiro m tal que 3m = k3 − k .
Queremos verificar que 3|(k + 1)3 − (k + 1). Note que
(k+1)3−(k+1) = (k2+2k+1)(k+1)−(k−1) = k3+3k2+3k+1−k−1 =
(k3 − k) + 3(k2 + k)
Como 3 divide (k3 − k) e 3(k2 + k), consequentemente 3 divide
(k + 1)3 − (k + 1). Desse modo P(k + 1) é verdadeira.
Indução Matemática
Exemplo 6
Use indução matemática para demonstrar a inequação
n < 2n
para todos os números inteiros positivos n.
Prova:
Considere P(n) como a proposição n < 2n para o número inteiro
positivo n.
PASSO BASE: P(1) é verdadeira, pois 1 < 21 = 2
PASSO DE INDUÇÃO: Assuma que P(k) é verdadeira, ou
seja, que k < 2k
Indução Matemática
Exemplo 6
Use indução matemática para demonstrar a inequação
n < 2n
para todos os números inteiros positivos n.
Prova:
Queremos verificar que P(k) é verdadeira. Ou seja, que
k + 1 < 2k+1. Primeiro adicionamos 1 em cada lado da inequação
de P(k) e temos que
k + 1 < 2k + 1.
Como 1 < 2k , pois k ∈ Z+. Temos que
k + 1 < 2k + 1 < 2k + 2k = 22k = 2k+1
. Desse modo P(k + 1) é verdadeira.
Indução Matemática
Exemplo 7
Use indução matemática para demosntrar a inequação
2n < n!
para todos os números inteiros positivos n ≥ 4.
	Introdução