Análise real/Indução

From Wikilivros
< Análise real
Jump to navigation Jump to search

Naturais[edit | edit source]

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)[edit | edit source]

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.

Exemplo[edit | edit source]

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 .

Exemplo1[edit | edit source]

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.

Exemplo2[edit | edit source]

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 3[edit | edit source]

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 4[edit | edit source]

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 5[edit | edit source]

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 6[edit | edit source]

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 7[edit | edit source]

Exemplo 8[edit | edit source]