Análise real/Indução

NaturaisEditar

O conjunto   é usado para contagens. De tão natural,   é chamado de conjunto dos números naturais, o primeiro conjunto numérico que aparece na história de qualquer civilização ou em qualquer tratado sobre os fundamentos da Matemática. Admitiremos conhecidos os conjunto   (dos números inteiros) bem como suas propriedades algébricas de soma e multiplicação e sua relação de ordem .

No conjunto   valem dois princípios fundamentais: o “Princípio da Boa Ordem” e o “Princípio da Indução”. Vamos provar mais adiante que são equivalentes.

Axiomas de Peano (sucessão)Editar

A função sucessão é dada por  

  1. (Identidade) A função de sucessão   é injetiva
    • Prova: Dados  .
  2. (Menor Elemento) Existe um elemento que não é sucessor de nenhum outro: 1
    • Prova: Suponha ser 1 o sucessor de um número natural t, assim   tal que  .
  3. (unicidade)  
    • Seja  , para cada equação temos que n=p e m=p; por transitividade n=m. Logo o sucessor de um número natural é único.
  4. (Princípio da Indução) Seja   um conjunto com as seguintes propriedades: Se  . Então  
O Princípio da Indução (e suas variantes) é usado para demonstrar que certas propriedades são verdadeiras para todo número natural. A estratégia é a seguinte. Definimos o conjunto A constituído pelos números naturais que possuem uma certa propriedade P. A seguir, mostra-se que A satisfaz as propriedades do princípio de indução. Daí, concluímos que   e, portanto, que P é verificada por todo número natural. Este tipo de argumento é chamado de demonstração por indução. É conhecido por indução finita pois existe a indução transfinita.

ExemploEditar

Vamos demonstrar, por indução, a conhecida fórmula  .

  • Mostraremos ser válida para n = 1 assim,  .
  • Suponhamos válido para n = k, ou seja, é verdadeiro que  .
  • Pela recíproca da lei do corte  .

Exemplo1Editar

Teorema:  

Prova
  • Vamos provar por indução sobre n:
    • Para quando n = 1, temos que  , então nossa soma é  .
    • Para quando n = 2, temos que  , então nossa soma é  .
    • Suponha ser válido para quando n=k, ou seja,  , então nossa soma é  .
    • Vamos provar ser válido para quando n=k+1, ou seja,  , então nossa soma é  .
      •    
      • onde as igualdades 1, 5 e 6 são pela propriedade distributiva, a propriedade 2 pela definição de termos ocultos numa soma, a igualdade 3 pela hipótese de indução e a igualdade 4 pela definição de multiplicação.
    • Portanto pelo princípio da indução é válido para todo n natural.

Exemplo2Editar

Teorema:  
Prova
  • Vamos provar por indução sobre n:
    • Para quando n = 1, temos que   (verdade).
    • Para quando n = 2, temos que   (verdade).
    • Suponha ser válido para quando n=k, ou seja,  .
    • Vamos provar ser válido para quando n=k+1, ou seja,  .
      •      
      • onde a igualdade 1 por definição de termo ocultos numa soma finita, a igualdade 2 é devido a hipótese de indução, a igualdade 3 por soma de frações, a igualdade 4 por evidência de um termo, as igualdades 5, 7 e 8 por distributiva, as igualdades 6 e 9 por associatividade da adição.
    • Portanto pelo princípio da indução é válido para todo n natural.

Exemplo 3Editar

Mostrar que, para todo   por indução sobre n.

Prova:

  • Mostrar que é válido para n = 1,   (verdade).
  • Supor válido para n = k, ou seja,  .
  • Mostrar válido para n = k+1, ou seja,  .
    •  
    •  
    • onde a igualdade 1 é pela hipótese de indução, a igualdade 2 é pela propriedade de potência e soma de frações, as igualdades 3, 4, 5 e 6 são pela propriedade distributiva, a igualdade 7 é pela comutativa e potência.

Exemplo 4Editar

Mostre que  
  • Prova por indução sobre n:
    • Mostrar que é válido para n = 1:  .
    • Supor válido para n = k:  
    • Mostrar válido para n = k+1, ou seja, Mostrar que  .
      • Temos que  .
      •  .
      • a igualdade 1 é devida à hipótese de indução, a igualdade 2 pela soma de frações e a igualdade 3 é pela propriedade distributiva.

Exemplo 5Editar

Mostre que  
  • Prova por indução sobre n:
    • Mostrar que é válido para n = 1:  .
    • Supor válido para n = k:  
    • Mostrar válido para n = k+1, ou seja, Mostrar que  .
      • Temos que  .
      •  
      • a igualdade 1 é devida à hipótese de indução, a igualdade 2 pela soma de frações, a igualdade 3 é pela propriedade redistributiva, a igualdade 4 é pela propriedade distributiva e a igualdade 5 pela lei do cancelamento.

Exemplo 6Editar

Teorema: Torre de Hanói (Para mover n discos para outra posição são necessário no mínimo   movimentos.

Prova (por indução):

  • Mostrar válido para n = 1:  
  • Supor válido para n = k:  
  • Mostrar válido para n = k+1 ou seja, mostrar que  .
    • Para isso devemos ter uma equação que relaciona a quantidade de movimentos com um disco a menos:
      • Para passarmos os discos de uma haste para outra, ocorre uma sequência bem simples:
        • Se temos n discos, devemos passar n-1 discos para outro haste;
        • depois passamos o disco maior para uma terceira haste;
        • depois passamos os n-1 discos para a terceira haste.
        • Por recorrência,  
    • Assim,  
      • onde a igualdade 1 é por recorrência, a igualdade 2 é pela hipótese de indução, a igualdade 3 é pela propriedade

Exemplo 7Editar

Exemplo 8Editar