Indução matematica

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

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

$[;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);]

(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)=;]

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

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

Adicionar comentário

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.

A Matemática Pura

Pesquisar este blog

Indução matematica - Parte I

Comentários

Postar um comentário