Mat Disc AULA06

Prévia do material em texto

Matemática Discreta - AULA06 - Prof. Rafael Matos 
 
Bibliografia utilizada: 
ROSEN, K. H. Matemática Discreta e suas aplicações. 
 
Tema: 
O princípio da indução matemática. 
Notação de somatório e exercícios sobre o princípio da indução matemática. 
 
Notas: 
 
Indução matemática 
 
É um método de prova matemática usado para demonstrar a verdade para um número infinito 
de proposições. A forma mais simples de indução matemática prova que um enunciado vale 
para todos os números naturais n. 
 
Uma prova por indução matemática de que P(n) é verdadeira para todo inteiro n consiste de 
dois passos: 
 
- Passo base: 
A proposição é verdadeira.(1)P 
 
- Passo indutivo: 
A implicação é verdadeira para todos os inteiros positivos k.(k) (k )P → P + 1 
 
Numa prova por indução matemática não é assumido que é verdadeiro para todos os (k)P 
inteiros, mas é mostrado que se for assumido que é verdadeiro, então também é (k)P (k )P + 1 
verdadeiro. 
 
Exemplo: 
Prove que, para todos inteiros , .n ≥ 1 ..1 + 2 + . + n = 2
n(n+1) 
 
Prova por indução matemática: 
Passo Base: , para , tem-se . Portanto, a fórmula é(1)P n = 1 1 = 2
1(1+1) ⇒ 1 = 1 
verdadeira para . n = 1 
Passo Indutivo: se a fórmula é verdadeira para , então deve ser verdadeira para n = k 
, ou seja, . n = k + 1 (k) (k )P → P + 1 
 
Supondo que a fórmula é verdadeira para , para algum inteiro : n = k k ≥ 1 
 
(i) ..1 + 2 + . + k = 2
k(k+1) 
 
E para : n = k + 1 
 
(ii) .. k )1 + 2 + . + k + ( + 1 = 2
(k+1)((k+1)+1) 
 
Como (i) é verdadeira, podemos aplicar em (ii): 
 
k )2
k(k+1) + ( + 1 = 2
(k+1)((k+1)+1) 
 
Resolvendo ambos os lados temos: 
2
k +3k+22 = 2
k +3k+22 
 
Portanto, prova-se que é verdadeira. 
 
Exercícios 
 
1 - Verifique se . Observe como com a afirmação é..0 + 1 + 2 + . + n = 2
n(n+2) n = 0 
verdadeira. 
 
2 - Prove que ...20 + 21 + . + 2n = 2n+1 − 1 
 
 
 
Notação de Somatório 
 
A notação de somatório permite simplificar a exibição de diversas somas. ​O operador utilizado 
para representar estas somas de vários (por vezes infinitos) termos, pode possuir as seguintes 
notações: 
 
..∑
n
k=m
ak = am + am+1 + . + an−1 + an 
ou 
(i) (m) (m ) .. (n ) (n)∑
n
i=m
f = f + f + 1 + . + f − 1 + f 
 
Onde: 
(sigma) ​= Representação do somatório∑
 
 
 
(índice do somatório) ​= Parte do ​limite inferior até o ​limite superior , / i k m n 
percorrendo todos os valores inteiros intermediários. As letras ​podem variar conforme a / i k 
necessidade de representação. 
 
Exemplo: Soma dos quatro primeiros números naturais. 
0∑
4
i=1
i = 1 + 2 + 3 + 4 = 1 
Cuja leitura é: somatório desde i = 1 até 4, de i. 
 
Propriedades de Somatório 
(i) (m)∑
m
i=m
f = f 
(i) (i) (i)∑
n
i=m
f = ∑
p
i=m
f + ∑
n
i=p+1
f 
Propriedade Aditiva 
(i) (i) (i) (i)∑
n
i=m
f ± g = ∑
n
i=m
f ± ∑
n
i=m
g 
Propriedade Homogênea 
 f (i) (i)∑
n
i=m
α = α ∑
n
i=m
f 
Propriedade Telescópica 
[ f (i ) (i)] (n ) (m)∑
n
i=m
+ 1 − f = f + 1 − f 
 
Alguns resultados de somatórios conhecidos 
∑
n
i=m
1 = n + 1 − m 
..∑
n
i=1
i = 1 + 2 + 3 + . + n = 2
n(n+1) 
..∑
n
i=1
i2 = 12 + 22 + 32 + . + n2 = 6
n(n+1)(2n+1) 
..∑
n
i=1
xi = x1 + x2 + x3 + . + xn = x−1
x(x −1)n 
 
Exercícios 
 
Calcule: 
a) ∑
20
i=1
3 + i 
b) i∑
10
i=0
5 + 2 
c) i∑
12
i=5
3 
d) 00∑
30
i=0
5 
e) ∑
∞
i=0
1
5i+1
− 1
5i
 
f) O valor de k para que seja verdade i 0k∑
20
i=0
2 = 1 ∑
20
i=1
i 
g) O valor de j para que seja verdade ∑
100
k=5
k = j + ∑
99
m=4
m