Matemática Discreta/Indução matemática

Indução Matemática

Indução matemática é um processo matemático de prova onde assume-se que um dado número possui uma propriedade e é demonstrado que o sucessor desse número também a possui. Se é possível mostrar que a prova é verdadeira para um dado número, a indução matemática assegura que ela também valerá para qualquer inteiro maior. Apesar de ser normalmente associada aos números naturais, a indução matemática pode ser empregada sempre que o conjunto em questão puder ser gerado por meio de definições indutivas. Por essa razão, apesar de possuir uma forma bastante similar ao método lógico de prova por introdução de condicional geral, pode ser aplicada a um domínio muito mais amplo.

Imagine o processo de indução matemática como a construção de uma fileira de dominós. A indução é usada geralmente quando se deseja provar que algo é verdade para qualquer número inteiro sem precisar provar para os infinitos casos particulares. Ela tem duas partes: enfileirar os dominós e, em seguida, derrubar o primeiro. Enfileirar os dominós deixando um espaço apropriado entre eles significa provar que se um qualquer cair, o próximo cairá. Derrubar o primeiro é provar que ele cai. Matemáticos chamam esses dois passos de "passo indutivo" e "passo básico", respectivamente.

Exemplo

Suponha que deseja-se provar que

$1+2+3+\cdots +n={\frac {n(n+1)}{2}}$

O que deve-se fazer é mostrar que SE isso é verdade para $k$, ENTÃO também o é para $k+1$.

Nota: Para provar uma afirmação condicional, assume-se que a condição é verdadeira e mostra-se que o consequente segue-se necessariamente.

Nesse caso, assumiremos $1+2+3+\cdots +k={\frac {k(k+1)}{2}}$ para um dado $k$. (Não! Isso não é raciocínio circular, embora possa parecer!)

O que precisamos mostrar é que, dada essa assunção, necessariamente:

$1+2+3+\cdots +k+(k+1)={\frac {(k+1)(k+1+1)}{2}}$

Como?

Olhemos apenas para o lado esquerdo da igualdade:

$1+2+3+\cdots +k+(k+1)$

Se substituirmos parte dele pelo lado direito da nossa assunção, ficamos com

${\frac {k(k+1)}{2}}+(k+1)$

Simplificando sucessivamente, chegamos a:

${\frac {(k*k+k)}{2}}+{\frac {(2k+2)}{2}}={\frac {(k*k+3k+2)}{2}}={\frac {(k+1)(k+2)}{2}}$

Ora:

${\frac {(k+1)(k+2)}{2}}$ é igual a ${\frac {(k+1)(k+1+1)}{2}}$

Logo, a afirmação é verdadeira.

O que acabamos de mostrar? Mostramos que SE a fórmula valer para $k$, ENTÃO ela valerá para $k+1$. Observe-se que não definimos exatamente quem era $k$. Isso significa que provamos que: se ela vale para 1, vale para 2; e se vale para 2, vale para 3; e se vale para 3, vale para 4; e assim por diante. Em outras palavras, concluímos a arrumação dos dominós. Mas não terminamos tudo ainda! Ainda não derrubamos nenhum dominói! Ainda há um passo restante: o caso básico. Precisamos derrubar o primeiro dominó. Quando n=1, 1+2+3+...+n é simplesmente igual a "1", e n(n+1)/2 equivale a 1(1+1)/2, que também vale 1. Logo, como 1=1, "o primeiro dominó caiu". Já que já mostramos que se a igualdade vale para 1, ela vale para dois e assim por diante, podemos deduzir que ela valerá para TODOS os naturais maiores que 1. Isso é indução matemática.

Há também uma versão chamada de indução forte, que é bastante parecida com a arrumação daquelas bonitas "árvores de dominós". Essencialmente, assume-se que a fórmula vale para todos os números até k e depois mostra-se que necessariamente ela também vale para k+1. Essa técnica é boa quando pode-se dividir o problema em um com menos partes, mas não necessariamente uma única.

Prátique mais e serás bem sucedido