O Princípio de Indução Completa

As ciências naturais utilizam o método chamado de indução empírica para formular leis que devem regar determinar fenômenos a partir de um grande número de observações particulares, selecionadas adequadamente. Este tipo de procedimento, embora não seja logicamente correto, é freqüentemente satisfatório: por exemplo, ninguém duvidaria de que quando um corpo é liberado ao seu próprio peso, no vácuo, na superfície da Terra, ele cai segundo a vertical local.

A validade de um teorema matemático se estabelece de forma totalmente diferente. Verificar que uma certa afirmação é verdadeira num grande número de casos particulares não nos permitirá concluir que ela é válida em geral. Com efeito, dada a expressão f(n) = n²-n+41, considere a seguinte afirmação: para cada inteiro positivo n, o valor de f(n) é um número primo (estamos supondo aqui que o leitor está familiarizado com a noção de número primo. Para n = 1 temos que f(1) = 41. Da mesma forma, f(2) = 43, f(3)=47, caso fossemos fazendo estas contas poderíamos verificar que a afirmação é verdadeira para os primeiros 40 valores de n. Porem para n= 41 temos que f(41) = 41x41 que não é um número primo. Consideremos então uma afirmação como a seguinte: a soma dos n primeiros inteiros positivos é igual a n(n+1), ou símbolos: 2

1 + 2 + 3 +...+ n - n(n+1)

2

Como verificar sua validade ? Evidentemente, é impossível demonstra-la em todos os casos particulares.

Para demonstrar a verdade deste tipo de propósito, que na realidade é uma seqüência infinita de proposições, uma para cada inteiro positivo - Introduziremos o chamado método de recorrência ou de Indução completa. Para isso, começaremos demonstrando o seguinte resultado:

Teorema - Sejam a um Inteiro dado e S um conjunto de inteiros maiores ou iguais a que tem as seguintes propriedades:

(i) a ÎS

(ii) Se um Inteiro k >= a pertence a S, então k+1 também pertence a S

Então S é o conjunto de todos os Inteiros maiores ou iguais a a

Demonstração

Suponhamos que a afirmação seja falsa. Então, o conjunta S’ dos Inteiros maiores ou iguais a a que não pertencem a S e não vazia (e limitado inferiormente por a). Conforme me a proposição existe m = mim S’.

Como a ÎS certamente a < a ="<">

Ainda, m-1 Ï S’, isto é, m-1 Î S. Conforme a propriedade (ii), ter-se-á então que m= (m-1)+i Î S, uma contradição, já que m Î S'.

Princípio de Indução Completa – 1ª.forma

Seja a um Inteiro dado. Suponhamos que para cada inteiro n >= a está dada uma afirmação A(n) de forma tal que:

(I) A(a) é verdadeira.

(II) Se para um Inteiro k>= a. A(k) é verdadeira, então A(k+1) é verdadeira.

Então a afirmação A(n) é verdadeira para todo Inteiro n >= a

Demonstração

Basta considerar o conjunto S dos Inteiros n >= a para os quais A(n) é verdadeira e verificar que está nas condições do teorema anterior. Assim, S contém todos os inteiros maiores ou iguais a a e segue a tese.

Exemplo - Provaremos agora que a formula

1 + 2 + ... + n =

é verdadeira para todo n >= 1

Para n= 1 a fórmula acima dá 1 = (1+1), 1=1.

2

Assim nossa afirmação é verdadeira para n=1. Deveremos mostrar agora que, se a afirmação é verdadeira para n= k, então também a verdadeira para n= k+1.

Estamos admitindo então como verdadeiro que

1+ 2 + ... + k = k( k+1)

2

Somando k + 1 a ambos os membros desta Igualdade temos:

1 + 2 +...+ k + (k+1) = k(k+1) + (k+1) a k(k+1) + 2(k+1)

2 2

é,

1 + 2 +...+k+(k+1) - (k+1) (k+2)

2

que é a fórmula correspondente a n = k+1, cuja validade queríamos demonstrar.