Matemática Discreta · 1.º ano (indicativo)

Como demonstrar por indução matemática passo a passo?

  • 9 min de leitura
  • 4 exemplos resolvidos
  • 5 exercícios com solução
  • Atualizado em

Resposta curta

Para provar que P(n) vale para todo o inteiro n ≥ n₀, faça duas coisas: (1) base — verifique P(n₀); (2) passo indutivo — suponha P(k) verdadeira (hipótese de indução) e, a partir dela, demonstre P(k+1). Provadas as duas, P(n) é verdadeira para todo n ≥ n₀.

Quando se aplica

A indução serve para provar afirmações sobre números inteiros a partir de um valor inicial: fórmulas de somas (1 + 2 + … + n), desigualdades (2n > n2 para n ≥ 5), divisibilidade (6 divide 7n − 1), propriedades de sequências definidas por recorrência. Não serve para encontrar a fórmula; serve para confirmar uma fórmula já conjeturada, por exemplo depois de testar casos pequenos.

A ideia, em palavras

Imagine uma fila de peças de dominó. Se a primeira cair (base) e se, sempre que uma cai, a seguinte também cai (passo indutivo), então todas caem. A base põe a primeira peça em movimento; o passo indutivo garante que a queda se propaga.

Pré-requisitos

  • Saber escrever P(k+1) a partir de P(k), substituindo n por k+1 em todo o lado.
  • Manipulação algébrica: fatorização, desenvolvimento de produtos, divisibilidade.
  • Distinguir hipótese (o que se supõe para n = k) de tese (o que se quer provar para n = k+1).

Esquema da indução

Base: P(n₀) é verdadeira. Passo: para todo k ≥ n₀, P(k) → P(k+1). Conclusão: P(n) é verdadeira para todo n ≥ n₀.

Método passo a passo

  1. Enuncie P(n) com precisão e diga a partir de que valor n₀ a afirmação deve valer.
  2. Prove a base: calcule os dois lados (ou verifique a propriedade) para n = n₀.
  3. Escreva a hipótese de indução: «Suponha que P(k) é verdadeira para um certo k ≥ n₀.»
  4. Escreva a tese: o que tem de provar, isto é, P(k+1), com n substituído por k+1.
  5. Parta de um dos lados de P(k+1) e use a hipótese de indução num ponto bem identificado, até chegar ao outro lado.
  6. Conclua: «Pelo princípio de indução matemática, P(n) é verdadeira para todo n ≥ n₀.»

Exemplos resolvidos

Exemplo 1 — Soma dos primeiros n inteiros

Enunciado: Prove que 1 + 2 + … + n = n(n+1)/2 para todo n ≥ 1.

Resolução:

  1. Base (n = 1): o lado esquerdo é 1; o direito é 1·2/2 = 1. Verdadeira.
  2. Hipótese: 1 + 2 + … + k = k(k+1)/2.
  3. Tese: 1 + 2 + … + k + (k+1) = (k+1)(k+2)/2.
  4. Pela hipótese: 1 + … + k + (k+1) = k(k+1)/2 + (k+1).
  5. Pondo (k+1) em evidência: (k+1)(k/2 + 1) = (k+1)(k+2)/2.

Resposta: a fórmula vale para todo n ≥ 1. Verificação: para n = 4: 1+2+3+4 = 10 e 4·5/2 = 10.

Exemplo 2 — Divisibilidade: 6 divide 7n − 1

Enunciado: Prove que 7n − 1 é divisível por 6 para todo n ≥ 1.

Resolução:

  1. Base (n = 1): 7 − 1 = 6, divisível por 6.
  2. Hipótese: 7k − 1 = 6m para algum inteiro m.
  3. Tese: 7k+1 − 1 é divisível por 6.
  4. Escreva 7k+1 − 1 = 7·7k − 1 = 7(7k − 1) + 7 − 1 = 7(7k − 1) + 6.
  5. Pela hipótese: 7·6m + 6 = 6(7m + 1), múltiplo de 6.

Resposta: 6 divide 7n − 1 para todo n ≥ 1. Verificação: n = 2: 49 − 1 = 48 = 6 × 8.

Exemplo 3 — Desigualdade com base diferente de 1

Enunciado: Prove que 2n > n2 para todo n ≥ 5.

Resolução:

  1. Base (n = 5): 25 = 32 e 52 = 25; 32 > 25. Verdadeira. (A base não é n = 1: para n = 3, 8 > 9 é falso.)
  2. Hipótese: 2k > k2, com k ≥ 5.
  3. Tese: 2k+1 > (k+1)2.
  4. Pela hipótese: 2k+1 = 2·2k > 2k2.
  5. Basta mostrar que 2k2 ≥ (k+1)2 = k2 + 2k + 1, ou seja, k2 ≥ 2k + 1. Para k ≥ 5: k2 = k·k ≥ 5k = 2k + 3k ≥ 2k + 15 > 2k + 1.
  6. Encadeando: 2k+1 > 2k2 ≥ (k+1)2.

Resposta: 2n > n2 para todo n ≥ 5. Verificação: n = 6: 64 > 36; n = 7: 128 > 49.

Exemplo 4 — Nível de exame: soma de potências de 2

Enunciado: Prove que 1 + 2 + 4 + … + 2n = 2n+1 − 1 para todo n ≥ 0.

Resolução:

  1. Base (n = 0): o lado esquerdo é 20 = 1; o direito é 21 − 1 = 1.
  2. Hipótese: 1 + 2 + … + 2k = 2k+1 − 1.
  3. Tese: 1 + 2 + … + 2k + 2k+1 = 2k+2 − 1.
  4. Pela hipótese: (2k+1 − 1) + 2k+1 = 2·2k+1 − 1 = 2k+2 − 1.

Resposta: a igualdade vale para todo n ≥ 0. Verificação: n = 3: 1+2+4+8 = 15 = 24 − 1.

Erros frequentes

  • Omitir a base. Sem base, o passo indutivo pode «provar» absurdos: se supusermos k = k + 1 e somarmos 1 aos dois lados, obtemos k + 1 = k + 2, mas a afirmação n = n + 1 é falsa para todo n.
  • Provar só a base ou só alguns casos. Verificar n = 1, 2, 3 não é demonstração.
  • Usar a tese como hipótese. Não pode supor P(k+1); só P(k).
  • Aplicar a hipótese fora de sítio, por exemplo substituindo uma parte que não tem a forma de P(k). Assinale o ponto exato onde a usa.
  • Errar na substituição n → k+1 (esquecer parênteses em (k+1)2, ou escrever 2k+1 em vez de 2k+1).
  • Começar a base no valor errado quando a propriedade só vale a partir de n₀ > 1, como no Exemplo 3.

Exercícios propostos

Tente resolver primeiro no caderno; depois confira.

1Exercício 1

Prove que 1 + 3 + 5 + … + (2n − 1) = n2 para todo n ≥ 1.

Ver dica

O termo novo na soma para n = k+1 é 2(k+1) − 1 = 2k + 1.

Ver solução

Base: n = 1: 1 = 12. Hipótese: 1 + 3 + … + (2k − 1) = k2. Tese: a soma até 2(k+1) − 1 = 2k + 1 é (k+1)2. Pela hipótese, a soma é k2 + (2k + 1) = (k+1)2. Fica provado.

2Exercício 2

Prove que 4n − 1 é divisível por 3 para todo n ≥ 1.

Ver solução

Base: 4 − 1 = 3. Hipótese: 4k − 1 = 3m. Então 4k+1 − 1 = 4(4k − 1) + 4 − 1 = 4·3m + 3 = 3(4m + 1), múltiplo de 3. Fica provado.

3Exercício 3

Prove que 12 + 22 + … + n2 = n(n+1)(2n+1)/6 para todo n ≥ 1.

Ver solução

Base: n = 1: 1 e 1·2·3/6 = 1. Hipótese: a soma até k é k(k+1)(2k+1)/6. Então a soma até k+1 é k(k+1)(2k+1)/6 + (k+1)2 = (k+1)[k(2k+1) + 6(k+1)]/6 = (k+1)(2k2 + 7k + 6)/6. Como 2k2 + 7k + 6 = (k+2)(2k+3), obtém-se (k+1)(k+2)(2k+3)/6, que é a fórmula com n = k+1.

4Exercício 4

Prove que n! > 2n para todo n ≥ 4.

Ver dica

A base é n = 4. No passo, use (k+1)! = (k+1)·k!.

Ver solução

Base: 4! = 24 > 16 = 24. Hipótese: k! > 2k, com k ≥ 4. Então (k+1)! = (k+1)·k! > (k+1)·2k ≥ 5·2k > 2·2k = 2k+1, porque k + 1 ≥ 5 > 2. Fica provado.

5Exercício 5

Uma sequência define-se por a₁ = 1 e aₙ₊₁ = aₙ + 2n + 1 (n ≥ 1). Calcule os primeiros termos, conjeture uma fórmula e prove-a por indução.

Ver solução

a₁ = 1, a₂ = 1 + 3 = 4, a₃ = 4 + 5 = 9, a₄ = 9 + 7 = 16. Conjetura: aₙ = n2. Base: a₁ = 1 = 12. Hipótese: aₖ = k2. Então aₖ₊₁ = k2 + 2k + 1 = (k+1)2. Fica provado.

Perguntas frequentes

Quando se usa a indução matemática?

Quando a afirmação depende de um inteiro n e a passagem de n = k para n = k+1 é natural, como em somas, produtos, divisibilidade e desigualdades. Se a afirmação não se «repete» de um valor para o seguinte, outro método (direto, contraposição, absurdo) é mais adequado.

O que é a indução forte e quando se usa?

Na indução forte supõe-se que P é verdadeira para todos os valores desde n₀ até k, e prova-se P(k+1). Usa-se quando P(k+1) depende de vários casos anteriores, por exemplo para mostrar que todo o inteiro n ≥ 2 é um produto de primos.

Existe um método mais rápido?

Para somas há por vezes uma dedução direta (a soma de Gauss, por exemplo), mas a indução é o método padrão para confirmar fórmulas conjeturadas e é muito pedida em exames. Em provas de divisibilidade, as congruências podem encurtar o trabalho.

A base tem de ser sempre n = 1?

Não. Tem de ser o menor valor para o qual a afirmação deve valer: n = 0 no Exemplo 4, n = 5 no Exemplo 3 e n = 4 no exercício das fatoriais. Escolher mal a base ou prová-la para um valor onde a afirmação é falsa invalida a demonstração.

Resumo

  • A indução tem duas partes obrigatórias: base e passo indutivo.
  • No passo, supõe-se P(k) (hipótese) e prova-se P(k+1) (tese); nunca se supõe a tese.
  • Escreva P(k+1) com cuidado, substituindo n por k+1 em todo o lado, e assinale onde usa a hipótese.
  • A base é o menor valor para o qual a propriedade deve valer, que nem sempre é 1.
  • Em desigualdades e divisibilidade, procure reescrever o termo de k+1 em função do de k.
  • A indução confirma fórmulas, não as descobre: teste casos pequenos para formular a conjetura.

Onde aprofundar

  • O programa da disciplina de Matemática Discreta ou Análise da sua instituição; no secundário, o manual de Matemática da classe e o programa oficial (INIDE / Ministério da Educação de Angola) — confirme a edição em vigor.
  • Kenneth Rosen, Discrete Mathematics and Its Applications, capítulo sobre indução e recursão.
  • Seymour Lipschutz, Matemática Discreta (coleção Schaum), com exercícios resolvidos de indução.

Continue a estudar

Ver tudo de Matemática Discreta