Posts com Tag ‘Discreta’

Indução Matemática:

1.Base: Provar que uma afirmação P(menor) é verdadeira
para o “menor” elemento sobre o qual incide a afirmação
2. Passo indutivo: Assumir que a afirmação é verdadeira
para P(k) com k=1, 2, …, n , então pode provar-se que:
P(n) → P(n+1) .
3. Conclusão: Usando 1. e 2. prova-se que: ∀n P(n)

Exemplo 01:
Provar que se n é um inteiro maior do que 1, então n pertence ao conjunto de números inteiros positivos.

1+2+3+4+…+n= n(n+1)/2 é verdadeiro ∀n Є Z+

Por indução matemática temos:

1. P(1) é verdadeiro? (primeiro valor da sequência)

1=1(1+1)/2
1=1 é verdadeiro

2.P(k) é verdadeiro? (último valor da sequência)

1+2+3+4…k=k(k+1)/2

Por demostrar que P(k+1) é verdadeiro
1+2+3+4…k+(k+1) = (k+1).((k+1)+1)/2

Temos que:

1+2+3+4…(k+1) = 1+2+3+4…(k+1)
= k*(k+1)/2 + (k+1)
= k (k+1) + (2(k+1))
= (k2+k+2k+2)/2
usando fatoração pelo método de Ruffine temos:

1 3 2

-1 -2
-1
1 2 0

(k+1)*(k+2)
=((k+1)*((k+1)+1))/2
logo
1+2+3+4+…+(k+1)=((k+1)-(k+1)+1)/2

isto é p(k+1) é verdadeiro.
Finalmente
de 1. e 2. por indução matemática temos;
p(n) é verdadeiro para todo n ou seja ∀n Є Z+
isto é, 1+2+3+4+…+n=(n(n+1))/2 é verdadeiro em ∀n Є Z+

Exemplo 02:
Provar que :
2^3n-1 é divisível por 7
Observação: um número mЄZ é divisível por rЄZ se e somente se existe tЄZ tal que m = r * t.

Exemplo 15(m) é divisível por 5(r) pois 15(m) = 5(r) * 3(t). “m” é divisível por “r” é equivalente a “m” é múltiplo de r.
Por indução matemática.

1.p(1) = 2^3*1-1 = 7 = 8 – 1 = 7 é divisível por 7, logo p(1) é verdadeiro.

2.Seja p(k) verdadeiro por demostrar que
p(k+1) é verdadeiro.
Temos:
2^3k-1 é divisível por 7
isto é 2^3k-1 = 7*t t Є Z
demostrando:
2^3(k+1)-1 = 2^3k+3-1
2^3(k+1)-1 = 2^3k * 2^3-1
2^3(k+1)-1 = 8 * 2^3k-1
2^3(k+1)-1 = 7 * 2^3k+2^3k -1
2^3(k+1)-1 = 7 * 2^3k+7 *t
2^3(k+1)-1 = 7 * (2^3k+t)
portanto:
3(k+1)
2^3(k+1)-1 = 7 * (2^2k+t)
isto é 2^3(k+1)-1 é divisível por 7 é verdadeiro.

Finalmente temos 1. e 2. é verdadeiro
2^3n-1 é divisível por 7 ∀n Є Z+

Esta é a primeira parte de indução matemática, as próximas postagens serão das aulas ministradas nas próximas semanas.

segue a lista de exercícios sobre conjuntos e indução matemática.
Lista 1 Matemática discreta.

Thiago Amorim