Indução matematica - Parte I

Postado por em
Olá, gente, hoje iniciarei uma seção em que darei algumas dicas importantes para a resolução de diversos problemas. Essa Seção ficará aberta para sempre, para que eu possa acrescentar artigos com alguma frequência. Como plano inicial, espero que até o final de Julho esta secção esteja com alguns artigos sobre métodos de demonstrações matemáticas e outras dicas bem importantes. Hoje falarei sobre o Principio da Indução Finita ou Método de Indução Matemática e suas variações.


Antes de explicar esse tema muito amplo, citarei alguns exemplos.
* mostre que: [;1+2+3+4+5+...+n= \frac{(n+1).n}{2} \forall n \ge 1;]
* mostre que: [;1^2+2^2+3^2+...+n^2= \frac{n \times(n+1) \times(2n+1)}{6} \forall n \ge 1;]
* mostre que: [;1^3+2^3+3^3+...+n^3= (1+2+3+...+n)^2 \forall n \ge 1;]


(Após demonstradas essas propriedades, tentem gravá-las e refazer as demonstrações, pois são bem importantes!)

O MIM ou PIF consiste basicamente em uma maneira de provar uma propriedade [;P(n);] para todo [;n \in \mathbb{N};] [;n\ge n_0;]. Para isso você deve verificar [;2;] coisas:

i) (Base da Indução, passo base ou passo básico) Verificar se [;P(n_0);] é verdadeira e
ii) (Passo indutivo) Verificar que se [;P(n);] é valido para algum n natural, [;n\ge n_0;], implica que [;P(n+1);] também é valido.

Em geral, há uma certa confusão pois pode parecer que é usar a hipótese para demonstrá-la, o que claramente não é valido, senão qualquer hipótese seria verdadeira. De forma mais didática, a demonstração pelo MIM equivale a demonstrar que, se vale para [;n_0;] e que se toda vez que vale para n, vale para seu SUCESSOR.


Por exemplo: imagine que eu subo uma escada, e que eu garanto que, se eu subir um degrau, então eu subirei mais um, com isso, eu subirei 2 degraus, e como eu subi 2, eu subirei 3 e assim por diante. Ao final, eu terei demonstrado que é possível subir uma escada de n degraus para todo n natural (a menos que eu fique cansado hahaha).

Vamos agora a mais alguns detalhes técnicos e exemplos.
No passo base, verificamos a validade dessa propriedade pra um valor inicial. A Hipótese de Indução (aqui no blog abreviarei para H.I.) é a propriedade aplicada a n, ou seja, [;P(n);], e o passo indutivo consiste em mostrar que, se a Hipótese é Válida para um n, então ela valerá para um n+1, mas veremos como funciona na prática.

*Mostre que: [;1+2+3+4+5+...+n= \frac{(n+1).n}{2} \forall n \ge 1;]

Primeiro, temos a base da indução,[; n=1;]


[;1= \frac{2.1}{2} = 1;]

Logo, o passo base é verdadeiro.



Depois, supondo que [;1+2+3+4+5+...+n= \frac{(n+1).n}{2};] seja verdadeiro para algum n, então

[;1+2+3+4+5+...+n+(n+1)= \frac{(n+2).(n+1)}{2};], de fato,

[;1+2+3+4+5+...+n+(n+1)= \underbrace{\frac{(n+1).n}{2}}_{1+2+3+4+5+...+n} + (n+1)= \frac{(n+1).n + 2(n+1)}{2};]

botando [;(n+1);] em evidência, [;\frac{(n+1)(n+2)}{2};]




C.Q.D.


Acho que com esse exemplo ficou claro como é feita a demonstração pelo MIM. Aqui vão mais dois exemplos para ajudar.
*Mostre que: [;1^2+2^2+3^2+...+n^2= \frac{n \times(n+1) \times(2n+1)}{6} \forall n \ge 1;]

Inicialmente, vamos mostrar o passo básico.

[;P(1) = 1^2= \frac{1 \times 2 \times 3}{6} = \frac{6}{6} = 1;]
Logo, o Passo básico é verdadeiro.

Nossa Hipotese de Indução é:


[;1^2+2^2+3^2+...+n^2=\frac{n \times(n+1) \times (2n+1)}{6};]

Vamos mostrar a veracidade do passo indutivo.


[;1^2+2^2+3^2+...+n^2+(n+1)^2 = \underbrace{\frac{n \times(n+1) \times(2n+1)}{6}}_{ = 1^2+2^2+3^2+...+n^2 } + (n+1)^2 =;]

[;\frac{n \times(n+1) \times(2n+1) + 6(n+1)^2}{6};]
Botando [;(n+1);] em evidencia e fazendo algumas contas...

[;\frac{(n+1) \times(2n^2 + n + 6n + 6)}{6};] porém [;(2n^2 + n + 6n + 6) = (2n+3)(n+2);], logo

[;1^2+2^2+ \cdots + n^2 + (n+1)^2=;][;\frac{(n+1) \times(n+2) \times (2n+3)}{6};]


que é exatamente nosso [;P(n+1);]

C.Q.D.


Uma boa dica é escrever como deve ficar seu [;P(n+1);] para que isso indique um possivel caminho para a solução do exercicio. Tal ideia será muito util na resolução do exercício a seguir.

*Mostre que: [;1^3+2^3+3^3+...+n^3= (1+2+3+...+n)^2 \forall n \ge 1;]


Passo Base. [;P(1)= 1^3 = (1)^2;] logo, o passo base está correto.

Passo Indutivo.


Inicialmente, para facilitar, temos que tentar entender quanto aumenta em relação a [;1+2+3+4+...+n)^2;] quando passamos para [;[1+2+3+4+...+n+(n+1)]^2;] , primeiro,
escreveremos
[;[1+2+3+4+...+n+(n+1)]^2 = [1+2+3+4+...+n+(n+1)] \times[1+2+3+4+...+n+(n+1)];] após isso, fica facil ver que:
[;[1+2+3+4+...+n+(n+1)]^2 - (1+2+3+4+...+n)^2 =;]
[;(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1);]

(é só ver que cada termo de 1 até n multiplica (n+1) 1 vez, depois (n+1) multiplica cada termo (incluindo n+1) 1 vez).

[;(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1)=;] [;2 \times [(n+1)+2(n+1)+3(n+1)+...+n(n+1)] + (n+1)(n+1);]

Isso é o dobro da soma dos termos de uma P.A de razão [;(n+1);], [;a_1= n+1;] e [;a_n= n(n+1);] (veja mais sobre P.A aqui) logo,
[;2 \times [\frac{[(n+1)(n+1)](n)}{2}] + (n+1)(n+1) = (n+1)^2 \times n + (n+1)^2 = (n+1)^3;]

Esse processo informalmente demonstra o teorema, porém como isso pode parecer usar a hipótese para demonstrar a hipótese, quero terminar com calma a demonstração.

Passo Indutivo (formalizado)
[;P(n+1)=;] [;1^3+2^3+3^3+...+n^3+(n+1)^3;]por Hipotese de Indução[;(1+2+3+4+...+n)^2 + (n+1)^3;]porém como mostramos acima,
[;(n+1)^3= (n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1).;]


Porém, como mostramos acima,
[;(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1);]
é a diferença [;[1+2+3+4+...+n+(n+1)]^2 - (1+2+3+4+...+n)^2;]
logo, [;(1+2+3+4+...+n)^2 + (n+1)^3 = [1+2+3+4+...+n+(n+1)]^2;]




C.Q.D.




Antes de terminar esse post, para que não fique muito longo, pois o assunto é bem extenso, eu gostaria de mostrar um erro comum ao usar o PIF.

Por exemplo, demonstrar que a soma dos n primeiros números ímpares é [;n^2 + 1;]
Definiremos um número ímpar como um número da forma [;2k-1;] (note que o n-ésimo número ímpar vale [;2n-1;]).

Nossa Hipotese de Indução é de que
[;1+3+5+...+(2n-1) = n^2 + 1;]
então
[;1+3+5+...+(2n-1)+(2n+1)= n^2 + 1 + 2n + 1 = (n+1)^2 + 1;]

CLARAMENTE ISSO ESTÁ ERRADO!

O erro é simples, o passo base não é valido, em geral, algumas pessoas não verificam o passo base por acharem muito trivial, mas não é e ele é tão importante quanto o passo indutivo.



Só por curiosidade, a soma dos n primeiros números ímpares é [;n^2;] e este é outro fato bem útil (para exercitar,tente demonstrar isso por indução).


Brevemente eu colocarei mais e mais coisas sobre o MIM . Para ler a parte II clique aqui
Até mais!



*** Lembre-se: Para melhorar a qualidade do nosso blog, avalie esse post.

Comentários

  1. DiogoColem19 de novembro de 2014 às 19:05

    Boa noite! Estou pesquisando alguns posts em Teoria dos Números e percebi que em vários deles as expressões não estão aparecendo. Há um motivo? Obrigado!

    ResponderExcluir
    Respostas
    1. A Matemática Pura26 de março de 2015 às 11:51

      Oi, Diogo!

      Infelizmente, é um problema recorrente em postagens antigas.
      Em breve vamos consertar tudo isso.

      Abraço,

      A Equipe do Blog.

      Excluir

Postar um comentário

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.