Livro de Matemática

Indução finita

A indução finita é uma técnica de demonstração matemática usada para provar que uma certa propriedade é verdadeira para todos os números naturais. Podemos usar como analogia uma fileira infinita de peças de dominó. Se dizemos que a primeira peça cai, com a garantia de que a queda de uma peça implica a queda da peça seguinte, teremos a certeza de que todas as peças cairão. Vejamos alguns exemplos:

Primeira Forma

Exemplo 1

Seja a ∈ N, e P uma propriedade, temos que:

  1. P(a) é verdadeira.
  2. Para k ≥ a, se P(k) é verdadeira, então P(k + 1) é verdadeira.

Nessas condições, P(n) é verdadeira para todo n ≥ a.

Exemplo 2

Seja a ∈ N, consideramos S o conjunto com as seguintes propriedades:

  1. a ∈ S.
  2. Para k ≥ a, se k ∈ S, então k + 1 ∈ S.

Nessas circunstâncias, S é o conjunto de todos os naturais maiores ou iguais a a.

Exemplos Resolvidos

  1. Dado n ∈ N, temos:
    0 + 1 + 2 + … + n =
    n (n + 1)
    2

    Primeiro devemos provar que a propriedade é verdadeira para o primeiro
    elemento, ou seja, o zero.

    0 =
    0 (0 + 1)
    2
    = 0

    Agora, assumimos que, para um k ∈ N a propriedade também é válida.
    Dessa forma temos:

    0 + 1 + 2 + … + k =
    k (k + 1)
    2

    Vamos agora provar a propriedade para um elemento k + 1. Já sabemos provar
    até um certo k.

    0 + 1 + 2 + … + k + k + 1 =
    k (k + 1)
    2
    + k + 1
    0 + 1 + 2 + … + k + k + 1 =
    k (k + 1)
    2
    +
    2 (k + 1)
    2
    0 + 1 + 2 + … + k + k + 1 =
    (k + 1)(k + 2)
    2
    0 + 1 + 2 + … + k + k + 1 =
    (k + 1)((k + 1) + 1)
    2

Indução Forte

Indução forte é uma variação do princípio da indução matemática, muito usada para provar afirmações sobre números naturais. A diferença entre indução fraca e indução forte está na hipótese de indução.

Diferença entre Indução Fraca e Forte:

Indução fraca: Você supõe que a propriedade é verdadeira para um número n, e prova que ela também é verdadeira para n + 1.

Indução forte: Você supõe que a propriedade é verdadeira para todos os números até n (ou seja, para 1,2,…,n), e prova que ela também é verdadeira para n + 1.

Estrutura da Indução Forte

Para provar que uma afirmação P(n) é verdadeira para todo n ≥ n0, você faz:

  • Motra que P(n0) é verdadeiro.
  • Supõe que P(n0), P(n0 + 1), …, P(k) são verdadeiros (hipótese de indução), e prove que P(k + 1) também é verdadeiro.

Exemplo 1

Provar que todo número natural n ≥ 2 pode ser escrito como produto de números primos.


Primeiro passo: provar que a propriedade é válida para n = 2.

2 é primo, portanto ele já é um produto de primos (ele mesmo).

Passo indutivo: suponhamos que todos os números de 2 até k podem ser escritos como produto de primos. Em seguida devemos provar que k + 1 também pode.

  • Se k + 1 é primo, então ele já é um produto de primos (ele mesmo).
  • Se k + 1 não é primo, então ele pode ser escrito como a * b, com 2 ≤ a, b ≤ k.

Como exemplo para visualizar melhor vamos supor que todos os números de 2 até 10 podem ser escritos como produto de primos e em seguida afirmamos que 11 também pode.

  • 2 é primo, logo o produto é ele mesmo.
  • 3 é primo, logo o produto é ele mesmo.
  • 4 → 2 * 2
  • 5 é primo, logo o produto é ele mesmo.
  • 6 → 2 * 3, sendo que 2 ≤ 2,3 ≤ 10
  • 7 é primo, logo o produto é ele mesmo.
  • 8 → 2 * 2 * 2, sendo que 2 ≤ 2 ≤ 10
  • 9 → 3 * 3, sendo que 2 ≤ 3 ≤ 10
  • 10 → 2 * 5, sendo que 2 ≤ 2,5 ≤ 10
  • 11 é primo, logo o produto é ele mesmo.

Exemplo 2

Considere a sequência definida pelos termos:

a1 = 1, a2 = 3, ak = ak – 2 + 2 ak – 1 com k ≥ 3.
Prove que an é ímpar para todo n ≥ 1.


Vamos escrever alguns termos dessa sequência.

a1 = 1

a2 = 3

a3 = a3 – 2 + 2 a3 – 1
a3 = a1 + 2 a2 = 1 + 2 * 3 = 7

a4 = a4 – 2 + 2 a4 – 1
a4 = a2 + 2 a3 = 3 + 2 * 7 = 17

Logo, a sequência possue a seguinte estrutura 1, 3, 7, 17, … .

Pela indução forte vamos provar para n de 1 até k. Para n = 1 e n = 2, o resultado é imediato, ou seja, a1 e a2 são ímpares.
Agora, assumimos que, para determinado k, os termos ai da sequência são ímpares, com 1 ≤ i ≤ k, e devemos provar que ak é ímpar.
Visto que nossa intensão é provar que até k os termos serão ímpares, logo ak – 2 e ak – 1 são ímpares, isto é, podem ser escritos, para certos r e s ∈ Z, como:

ak – 2 = 2r + 1

ak – 1 = 2s + 1

Logo:

ak = ak – 2 + 2 ak – 1
ak = (2r + 1) + 2(2s + 1)
ak = 2r + 1 + 4s + 2
ak = 2r + 4s + 2 + 1
ak = 2(r + 2s + 1) + 1
ak = 2t + 1, sendo t = r + 2s + 1

Portanto, ak é ímpar como objetivamos provar.