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 esta conta poderia 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:

            a (S

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 demonstrar.

Exemplo - Mostraremos agora um resultado da geometria do plano:” a soma dos ângulos de um polígono convexo de n lados Sn = (n-2) x 180°, n >= 3”

De fato, para n = 3 temos que o polígono convexo correspondente é um triângulo e sabemos da geometria elementar que a soma dos seus ângulos é 180°

Suponhamos a afirmação valida para n = k >= 3, isto é que a soma dos ângulos de um polígono convexo com k lados é Sk = ( k-2 ) x 180°

0 polígono a0a2...a k que se obtém traçando o segmento a0a2 tem k lados; consequentemente, a soma dos seus ângulos é  Sk = (k-2) x 180°.

Agora, a soma dos ângulos do polígono original será Sk mais a soma dos ângulos do triângulo a0a1a2 isto é, Sk+1 = Sk + 180° = (k-2) 180° + 180° =(k-1) 180°.

Exemplo - Considere a formula 2n3 > 3n2+3n+1. 0 leitor poderia verificar diretamente que ela é falsa para n=1 e n=2. Porem, para n=3 obtemos: 54 > 34 que é uma afirmação verdadeira.

Suponhamos então que a afirmação é verdadeira para n = k >= 3, isto é, que 2k3 > 3k2 + 3k + 1.

Tentaremos demonstrar que a afirmação também é verdadeira para n = k+1 isto é, que

            2(k+1)³  >  3(k+1)² + 3(k+1) + 1

Temos que:

2(k+1)³ = 2(k³ +3k² +3k+1) = 2k³ + 6k²+6k+2

Usando a hipótese de indução, vem:

            2(k+1)³            >            3k²+3k+1+6k²+6k+2 = 3(k²+2k+1)+3k+6k2 = 3(k+1)²+3k+6k.

Como k >=3 temos que 6k² >= 54 > 3+1 e substituindo na fórmula acima temos:

2(k+1)³  >  3(k+1)² + 3k + 3+1= 3(k+1) + 3(k+1) + 1 como queríamos demonstrar.

Podemos afirmar então que a fórmula dada  é válida, para todo inteiro maior ou igual a 3.

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

(i)         a ( S

(ii)        Se k e um inteiro positivo tal que todo inteiro m verificando a =< m =< k pertence a S, então k + 1  pertence a S.

Então,  S é o conjunto de todos os inteiros maiores ou iguais a a.

Demonstração

Suponhamos que a afirmação é falsa. Então, o conjunto S’ dos inteiros maiores ou iguais a a, que não pertencem a S, é vazio e limitado inferiormente. Conforme a proposição, existe m = mim S’, pela condição (i) certamente m > a, logo

( m –1 ) + 1 = m pertence a S; uma contradição.

Principio de Indução Completa – 2ª forma

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

 A (a) é verdadeira.

 Se A(m) é verdadeira para todo inteiro m tal que a =< m =< k então A(k+1) é verdadeira.

Então A(n) é verdadeira para todo inteiro  n >= a

Exemplo – Vamos definir uma seqüência da seguinte forma: só dois primeiros termos serão a1 = 1 e a2 = 3; cada um dos termos subsequentes se define como a soma dos dois anteriores, isto é, an = an-1  + an-2. Assim, os primeiros termos desta seqüência serão:

            1, 3, 4, 7, 11, 18, 29, ...

Queremos demonstrar que, para cada n, vale a desigualdade:

            an  <  ()n

De fato, para n =1 temos 1 < () e para n =2 temos 3 < ()2.

Seja então k >= 2 e suponhamos agora que ela vale para todo inteiro positivo menor ou igual a k. Queremos provar que ak+1 = ak + ak-1.

Da hipótese de indução, a afirmação vale, em particular, para n =k e n = k-1. Logo, temos ak < ()k e ak-1 < ()k-1, donde temos:

ak+1 <  ()k + ()k-1 = ()k-1 ( + 1) = ()k-1 *

Como ainda   < ()2 temos que:

ak+1 <  ()k-1 * ()2 = ()k+1 , como queríamos demonstrar.

A indução completa fornece também um método para definir novos conceitos, método de recorrência. Por exemplo, dado um inteiro a podemos definir potência de a expoente positivo da seguinte forma:

  a1= a;

Para cada inteiro positivo n, definimos an+1 = a * an.

O par de condições acima dá um regra que especifica o significado só símbolo an para cada inteiro n >= 1. Por convenção definiremos ainda a° = 1.

O método de recorrência também é usado para definir o símbolo n!. Definimos:

1!  = 1

n!  = n * [ ( n - 1 )! ] para todo inteiro n >= 1.

Assim temos que 1! = 1, 2! = 2*1, 3! = 3*2*1 e, em geral, n! é o produto de todos os números positivos menores ou iguais a n.

O uso do principio de indução completa com método de demonstração parece ser muito antigo e está implícito na obra de Euclides. Aceita-se freqüentemente que a primeira formulação explícita deste princípio se deve a Blaise Pascal em 1654. O nome “indução  matemática” surgiu bem mais tarde. Apareceu pela primeira vez em 1838 por Morgan.

Demonstrações

Provar que Kn  ( Grafo Completo ) é igual

Hipótese | E ( Kn  ) | =

| E ( Kn+1 ) | =

Subgrafo

Se ele formar um grafo completo terá 6 arestas para n=4 ( base ). Se acrescentarmos mais 1 ponto (n + 1), o grafo terá 6 arestas + n arestas.

Com referência o grafo acima, quando acrescentamos aos n pontos distribuídos sobre a circunferência um novo ponto P e o ligamos a um dos pontos anteriores, obtemos tantas novas regiões quantas forem as interseções do novo segmento, com os anteriores, mais uma. para calcular o número de interseções, vamos enumerar os n pontos de 1 a n, no sentido anti-horário, a partir de P. O segmento que parte de P e vai ao j-ésimo ponto intersecta todos os segmentos que ligam os j-1 pontos anteriores ao

j-ésimo com os n - j pontos posteriores ao j-ésimo; o número de tais intersecções é portanto, (j -1)(n -j) e, assim, o número de novas regiões correspondentes ao j-ésimo ponto é:

(j - 1)(n -j) + 1.

Somando para j = 1, 2, ... , n, obtém-se o número P(n) de novas regiões, quando passamos de n para n + 1 pontos sobre a circunferência:

P(n) =

Quando n=1, temos uma única região; ao passarmos de n = 1 para n = 2, acrescentamos P(1) = 1 nova região, de modo que:

R2 = 1 + P(1) = 2.