Aula 9 inducao matematica ii

1. Curso: Ciência da Computação
Turma: 3º/4º Semestre
Matemática Discreta
Aula 8
Indução Matemática
Revisão para a Prova

2. Matemática Discreta
2/8
Notas de Aula
✔
O conteúdo da aula de hoje está no capítulo 2 do livro
do Gersting.
✔
Correção da prova.

3. Matemática Discreta
3/8
Indução Matemática
1. P(1) é verdadeira
2. P(r) é verdadeira para todo r
1≤ r≤ k → P(k+1) verdadeira

4. Matemática Discreta
4/8
Ideias Principais
Indução matemática é uma técnica usada para
demonstrar propriedades de números inteiros
positivos.
Uma demonstração por indução não precisa
começar no valor 1.
A indução pode ser usada para demonstrar
resultados sobre quantidades, cujos valores são
inteiros não-negativos arbitrários.
A indução fraca e a indução forte podem ser usadas
para demonstrarem o mesmo resultado; no
entanto, dependendo da situação, uma ou outra
abordagem pode ser mais fácil de ser utilizada.

5. Matemática Discreta
5/8
Prove que 1+3+5+...+(2n - 1) = n
2
para todo inteiro
positivo n
Primeiro preciso provar para n = 1
P(1) → 1 = 1
2
OK
Vamos provar para n = 4 também.
P(4) → 1+3+..+(2*4-1) = 4
2
1+3+5+7 = 16 OK
Assumimos que é verdade para n
P(n) → 1+3+5+...+(2n - 1) = n
2
(Hipótese da indução)
Precisamo provar para n+1
P(n+1) → 1+3+5+...+(2n – 1) + (2(n+1) - 1) = (n+1)
2
Desenvolvendo o primeiro termo da equação
1+3+5+...+(2n – 1) + (2(n+1) – 1) = (substituindo 1+3+5+...+(2n – 1) por
n
2
pela hipótese da indução) n
2
+ 2n + 2 – 1 = n
2
+ 2n + 1 = (n+1)
2
CQD.

6. Matemática Discreta
6/8
Prove que n
2
≥ 3n para todo n ≥ 4
Como n começa em quatro precisamos provas a desigualdade para n=4
P(4) → n
2
≥ 3n → 4
2
≥ 3*4 → 16 ≥ 12
A partir da prova para P(4) assumimos que é verdade para P(n)
P(n) → n
2
≥ 3n
Precisamos provar para n+1
P(n+1) → (n+1)
2
≥ 3(n+1) → n
2
+ 2n +1 ≥ 3n + 3
resolvendo somente o primeiro termo da equação
n
2
+ 2n +1 > 3n + 2n + 1 (pela hipótese da indução pois n
2
≥ 3n)
≥ 3n + 8 + 1 (já que n ≥ 4)
> 3n + 3
= 3(n+1)
Portanto n
2
+ 2n +1 ≥ 3n+3)

7. Matemática Discreta
7/8
Prove que 1+2+2
2
+...+2
n
= 2
n+1
– 1 para qualquer n ≥ 1
Precisamos provar para n=1
P(1) → 1+2
1
= 2
(1+1)
– 1 → 3 = 3 OK.
Assumimos que é verdade para n
P(n) → 1+2+2
2
+...+2
n
= 2
n+1
– 1
Precisamos provar para n+1
P(n+1) → 1+2+2
2
+...+2
n
+ 2
(n+1)
= 2
(n+1+1)
– 1
Resolvendo o primeiro termo da equação
1+2+2
2
+...+2
n
+ 2
(n+1)
= 2
(n+1)
-1 + 2
(n+1)
= 2(2
(n+1)
) – 1 que é igual
ao 2º termo da P(n+1) → 2
(n+2)
- 1

8. Matemática Discreta
8/8
Exercícios
1. Prove por indução
(a) 1+2+3+...+n = n(n+1)/2
(b) 1.1! + 2.2! + … + n.n! = (n+1)! -1
(c) 2
n
≥ n
2
para n ≥ 5
(d) (1+x)
n
> 1 + x
n
2. O que está errado na demonstração por indução
matemática? Iremos provar que n é igual a 1 + n.
Suponha que P(n) é verdadeira.
n = n+1
somando 1 a ambos os lados
n+1 = n+2 logo P(n+1) é verdadeira