O princípio da indução completa

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 < m, logo a =< m-1< m

Ainda, m-1 <m - min S’, logo 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.

Exemplo (Soma dos termos de uma progressão aritmética)

Sejam a e r dois números inteiros. A seqüência a1 = a, a2 = a + r, a3 = a + 2r, ... an = a + (n-1) r, ... diz-se uma progressão aritmética de razão r. Provaremos que a soma dos n primeiros termos de uma progressão aritmética é:

a + (ar) + ... +(a +(n-1)r) - n (2a + (n-1) r)

2

Com efeito: para n =1 , a fórmula é:

a =1 *

é, para n a 1 é verdadeira.

Suponhamos agora que a formula vale para n =k, isto é, admitimos que vale:

a + (ar)+...+(a +(k-1)r) – k(2a+(k-1)r)

2

Somando a+ Kr a ambos os membros desta igualdade temos:

a+(ar)+... (a+(k-1)r) + (a+kr) = k(2a+(k-1)r) +(a+kr)

2

= k(2a+(k-1)r)-+-2(a+kr) = 2ak + k(k-1)r +2a+2kr =

2 2

= 2a(k+1) + Kr(k-1+2) = 2a(k+1) + Kr(k+1) =

2 2

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

2

a + (ar) + ... +(a+kr) a (k+1)(2a+kr)

2

que é a formula correspondente a n a k+1, cuja validade queríamos