Saltar para o conteúdo

Análise real/Indução

Origem: Wikilivros, livros abertos por um mundo aberto.

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 | editar código-fonte]

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.

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 .

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