Matemática Discreta Unidade E – Seqüências, Indução Matemática e Relações de Recorrência

Indução Matemática

Indução Matemática é uma técnica de prova matemática usado para demonstrar a verdade de um número infinito de proposições. A forma mais simples e mais comum de indução matemática prova que um enunciado vale para todos os números naturais n e consiste de dois passos:

1. A base: mostrar que o enunciado vale para n = 1.
2. O passo indutivo: mostrar que, se o enunciado vale para n = k, então o mesmo enunciado vale para n = k + 1.

Esse método funciona provando que o enunciado é verdadeiro para um valor inicial, e então provando que o processo usado para ir de um valor para o próximo é valido. Se ambas as coisas são provadas, então qualquer valor pode ser obtido através da repetição desse processo. Para entender por que os dois passos são suficientes, é útil pensar no efeito dominó: se você tem uma longa fila de dominós em pé e você puder assegurar que:

1. O primeiro dominó cairá.
2. Sempre que um dominó cair, seu próximo vizinho também cairá.

Então você pode concluir que todos os dominós cairão.

Observe como fazer, assistindo a apresentação em PowerPoint:

Exemplos de Indução

Exercícios de Indução

1 ) Prove por indução que, para qualquer n N:

a) 2+4+6+.....+2n=n(n+1)

b) 1+3+5+...+(2n – 1) = n², ou seja, que a soma dos n primeiros números ímpares é  n².