Pular para o conteúdo principal

Como fazer demonstrações por indução matemática

No famoso post onde explico como fazer demonstrações, eu expliquei as três técnicas mais comuns: a demonstração direta, a demonstração por absurdo e a demonstração por contraposição. Alguns meses depois, muitos leitores gentilmente me lembraram que ficou faltando a demonstração por indução, que é a que vamos explicar agora.



Efeito dominó


A demonstração por indução lembra, em muito, o efeito dominó: aquele jogo onde você enfileira vários dominós, bate no primeiro e a sua queda causa a queda dos demais. Para que essa brincadeira dê certo, precisamos de garantir duas coisas fundamentais: primeiro, que o toque que vamos dar na primeira peça seja forte o suficiente para fazê-la cair; segundo, que a distância entre as pedras seja tal que possibilite que uma que caia possa derrubar a seguinte.


Se qualquer uma dessas condições falhar, nosso jogo não dará certo: se nosso toque na primeira pedra for fraco, ela não cairá e nada acontecerá; se a distância das pedras não for tal que garanta que a queda de uma cause a queda da seguinte, corremos o risco de apenas a primeira - ou apenas algumas - ser derrubada.


O princípio da indução matemática é a mesma coisa. Primeiro, precisamos garantir que uma proposição p(n) seja verdadeira (o nosso toque inicial) e, depois, devemos nos assegurar que, se dado um k qualquer, sendo k maior do que n, a implicação p(k) é verdadeira implique que p(k+1) é verdadeira.


Matematicamente, essas nossas garantias recebem nomes especiais. Nossa condição de que p(n) seja verdadeira chama-se base de indução; A condição de que p(k) seja verdadeira é chamada de hipótese de indução e sua implicação recebe o nome de passagem de indução.


Vamos mostrar como a indução funciona na prática. Provaremos que, para todo n inteiro positivo, vale que 1/(1.2) + 1/(2.3) + ... + 1/(n(n+1)) = n/(n+1). A princípio, temos dificuldades em imaginar como poderíamos demonstrar a igualdade pelos métodos usuais, então, vamos utilizar a demonstração por indução!


Base de indução: p(1) = 1/1.2 = 1/2 = 1/(1+1) (OK!)


Hipótese de indução: Agora que já sabemos que p(1) é verdadeira, ou seja, conseguimos derrubar nosso primeiro dominó, vamos supor que p(k) é verdadeira, isto é, 1/1.2 + 1/2.3 + ... + 1/k(k+1) = k/(k+1). Com base em nossa hipótese, vamos verificar se p(k+1) também é verdadeira. Assim, temos que:


p(k+1)


Reorganizando a expressão, temos:


Reorganizando p(k+1)


Perceba que o que está dentro do parênteses é exatamente a nossa hipótese de indução! Dessa forma, podemos reescrever a equação substituindo o conteúdo do parênteses por k/(k+1), conforme você vê no segundo termo da igualdade.


Fazendo o clássico MMC com a expressão resultante e utilizando-se de nossos conhecimentos em produtos notáveis, obtemos:


Fazendo o MMC


E simplificando a igualdade, chegamos a:


... finalmente!


Assim, concluímos que p(k + 1) é verdadeira. Logo, pelo princípio da indução, concluímos que p(n) é verdadeira para todo n inteiro maior ou igual a 1.


Vale notar, ainda, dois pontos interessantes: aqui utilizamos p(1) para nossa base de indução, mas isso não é uma regra: dependendo do problema, a base pode assumir outro valor, como 0 ou algum outro número. Além disso, a indução é uma característica exclusiva do conjunto dos números Naturais: ela não pode ser aplicada quando estamos lidando com números decimais ou irracionais, por exemplo.


Com isso, concluímos - por enquanto - nossos artigos sobre demonstração. Espero que, com eles, você possa ter mais facilidade de entender seu curso. Boa sorte!

Comentários

  1. ....fiz uma boa busca, boa informacao......

    ResponderExcluir
  2. Tive uma boa. Informação que precisava obrigado

    ResponderExcluir
  3. markuz bize bezerra claudino22 de setembro de 2014 03:39

    e podes, min indicar livros sobre o assunto,
    e enviar, mas teoria(pratica), sobre indução matemática,
    e porque a indução lembra o efeito dominó, apesar, o que
    li, é muito interessante.
    claudino.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Como acessar configurações avançadas no Sagemcom F@st 2704N

NOVO TUTORIAL: GUIA DEFINITIVO DAS CONFIGURAÇÕES AVANÇADAS DO SAGEMCOM F@ST 2704N!
Atualização 23/01/2015: Alguns problemas apontados e descobertos nesse modem:
1. Alguns usuários relatam dificuldade em salvar alterações na configuração ADSL;
2. Não sei como acessar os logs do modem; mesmo habilitando, eles não aparecem;
3. Se você trocar o DNS do modem, ele voltará ao da Oi ao ser reiniciado;
4. Estou enfrentando alguns problemas sérios de lentidão. Não sei se isso é relacionado ao modem ou a algum dispositivo na minha rede interna.
-----
Os modens da marca Sagemcom estão se tornando muito populares no Brasil, não, quiçá, por sua qualidade, mas porque eles são os atuais queridinhos das operadoras: quando você assina um plano ADSL, geralmente a operadora envia um modem wireless para sua casa a fim de que você possa navegar sem precisar ter gastos extras com esse equipamento. É claro que os equipamentos fornecidos pelas operadoras são básicos, mas saciam as necessidades dos usuários comuns - …

O Guia Definitivo das configurações avançadas no Sagemcom F@st 2704N

Há alguns meses, eu contei minha experiência com o Sagemcom F@st 2704N e tenho recebido diversos comentários sobre suas configurações avançadas. Agora que minhas aulas na faculdade estão acabando, resolvi reservar um tempinho para explorar melhor esse modem que, diga-se de passagem, é muito bom.