trabalho de SD

UNIVERSIDADE FEDERAL DE PELOTAS
CURSO DE CIÊNCIA DA COMPUTAÇÃO
CURSO DE ENGENHARIA DE COMPUTAÇÃO

Sistemas Discretos I
Prof. Aline Brum Loreto
****************************************************************************************

Indução e Recursão
O Princípio da Indução Matemática é uma técnica para lidar com tipos de dados que têm uma relação de boa-ordem, isto é, uma relação onde todo subconjunto não vazio do tipo de dado tem um elemento mínimo segundo essa relação de ordem. Por exemplo, o conjunto dos números naturais (um tipo de dado), onde dada uma boa ordem, pode-se aplicar indução para provar propriedades que valem para todo elemento do tipo de dado.
Exemplo- Princípio da Indução Matemática: Efeito dominó, onde uma fila sem fim de peças do jogo dominó para a qual, ao derrubar a primeira peça, todas as demais peças são derrubadas em cadeia. Para estar certo de que tal fato ocorre, suponha que são verdadeiras as seguintes proposições:
a) A primeira peça é derrubada na direção das demais;
b) Se qualquer peça está suficientemente próxima da seguinte na fila, então, ao ser derrubada, fará com que a sua vizinha também seja derrubada.
Então:
- pelo item a), a primeira peça é derrubada;
- pelo item b), a segunda peça é derrubada;
- pelo item b), a terceira peça é derrubada;
- pelo item b), a quarta peça é derrubada;
- e assim sucessivamente.
Portanto, para i tão grande quanto se queira, pode-se afirmar que a i-ésima peça é derrubada.
Logo, para qualquer n, pode-se afirmar que a n-ésima peça é derrubada.
O Princípio da Indução Matemática pode ser resumido como segue:
Se o início é correto e se coisa alguma pode dar errada, então sempre será correto.
Definição – Princípio da Indução Matemática
Seja p(n) uma proposição sobre M={n ∈N n ≥ m e m ∈ N}. O Princípio da Indução
Matemática é como segue:
a) p(m) é verdadeira;
b) para qualquer k∈ M, vale p(k) ⇒ p(k+1)
c) então, para qualquer n ∈ M, p(n) é verdadeira.
1

Nesse caso,