Note que às vezes é difícil localizar o erro em uma demonstração falsa por indução matemática, como ilustra o Exemplo 14.
EXEMPLO 14 Encontre o erro nesta “demonstração” de uma afirmação claramente falsa de que todo conjunto de retas em um plano, não paralelas duas a duas, encontram-se em um ponto comum.
“Demonstração”: Considere P(n) como a proposição que afirma que todo conjunto de n retas no plano, as quais não são paralelas duas a duas, encontram-se em um ponto comum. Vamos demonstrar que P(n) é verdadeira para todos os números inteiros positivos n \geq 2.
PASSO BASE: A proposição P(2) é verdadeira, pois duas retas quaisquer no plano que não são paralelas encontram-se em um ponto comum (pela definição de retas paralelas).
PASSO DE INDUÇÃO: A hipótese indutiva é a proposição que afirma que P(k) é verdadeira para todo número inteiro k, ou seja, é a hipótese de que todo conjunto com k retas no plano, das quais duas delas não são paralelas, encontram-se em um ponto comum. Para completar o passo de indução, devemos mostrar que se P(k) é verdadeira, então P(k+1) deve ser verdadeira também, ou seja, devemos mostrar que se todo conjunto de k retas no plano, das quais duas delas não são paralelas, encontram-se em um ponto comum, então todo conjunto de k+1 retas no plano, das quais duas delas não são paralelas, encontram-se em um ponto comum. Assim, considere um conjunto de k+1 retas distintas no plano. Pela hipótese indutiva, as k primeiras dessas retas encontram-se em um ponto comum p_{1}. Além disso, pela hipótese indutiva, as k últimas dessas retas encon-tram-se em um ponto comum p_{2}. Mostraremos que p_{1} e p_{2} devem ser o mesmo ponto. Se p_{1} e p_{2} fossem pontos diferentes, todas as retas com ambos deveriam ser a mesma reta porque dois pontos determinam uma reta. Isso contradiz nossa hipótese de que todas essas retas são distintas. Assim, p_{1} e p_{2} são o mesmo ponto. Concluímos que o ponto p_{1}=p_{2} para todas as k+1 retas. Mostramos que P(k+1) é verdadeira, assumindo que P(k) seja verdadeira, ou seja, mostramos que se assumimos que todas as retas distintas k, k \geq 2, encontram-se em um mesmo ponto, então todas as retas distintas k+1 encontram-se em um ponto comum. Isso completa o passo de indução.
Completamos o passo base e o de indução e supostamente temos uma demonstração correta por indução matemática.
Solução: Examinando esta suposta demonstração por indução matemática, parece-nos que tudo está em ordem. Entretanto, há um erro particularmente sutil. Olhando com cuidado para o passo de indução, vemos que esse passo requer que k \geq 3. Não podemos mostrar que P(2) implica P(3). Quando k=2, nosso objetivo é mostrar que três retas distintas quaisquer encontram-se em um ponto comum. As primeiras duas retas encontram-se em um ponto comum p_{1}, e as duas outras retas devem encontrarse em um ponto comum p_{2}. Mas nesse caso, p_{1} e p_{2} não precisam ser o mesmo ponto, porque apenas a segunda reta é comum a ambos os conjuntos de retas. Aqui é onde o passo de indução falha.

Exercícios

  1. Há “infinitas” estações em uma rota de trem. Suponha que o trem pare na primeira estação e que, se ele pára em uma estação, pára também na próxima. Mostre que o trem pára em todas as estações.
  2. Suponha que você saiba que um jogador de golfe acerta o primeiro buraco de uma seqüência com um número infinito de buracos, e que, se esse jogador acertar um buraco, então acertará o próximo também. Demonstre que esse jogador acerta todos os buracos da seqüência.
    Use a indução matemática nos exercícios 3 a 17 para demonstrar as fórmulas de somatório.
  3. Considere P(n) como a proposição de que 1^{2}+2^{2}+\cdots+n^{2} =n(n+1)(2 n+1) / 6 para todo número inteiro positivo n.
    a) Qual é a proposição P(1) ?
    b) Mostre que P(1) é verdadeira, completando o passo base da demonstração.
    c) Qual é a hipótese indutiva?
    d) O que você precisa para demonstrar o passo de indução?

Passo 1

O enunciado define P(n) como a proposição
1^{2}+2^{2}+\cdots+n^{2}=\frac{n(n+1)(2n+1)}{6}
e pede que usemos indução matemática para os itens (a)–(d) referentes a n=1 e ao passo de indução.

Passo 2

Para (a) e (b) tratamos do passo base n=1.
A proposição P(1) afirma que
1^{2} \;=\;\frac{1\cdot(1+1)\cdot(2\cdot1+1)}{6}.
O lado esquerdo vale 1. O lado direito vale
\frac{1\cdot2\cdot3}{6}=\frac{6}{6}=1.
Logo, P(1) é verdadeira.

Passo 3

Para (c), a hipótese indutiva consiste em assumir que, para um inteiro k\ge1,
1^{2}+2^{2}+\cdots+k^{2}=\frac{k(k+1)(2k+1)}{6}.

Passo 4

Para (d), no passo de indução precisamos mostrar que essa hipótese implica
1^{2}+2^{2}+\cdots+k^{2}+(k+1)^{2} =\frac{(k+1)\bigl((k+1)+1\bigr)\bigl(2(k+1)+1\bigr)}{6}.

Resposta

(a) P(1) é a afirmação
1^{2}=\frac{1\cdot2\cdot3}{6}.
(b) Verifica-se que 1^{2}=1 e \tfrac{1\cdot2\cdot3}{6}=1, logo P(1) é verdadeira.
(c) A hipótese indutiva é assumir que
1^{2}+2^{2}+\cdots+k^{2}=\frac{k(k+1)(2k+1)}{6}.
(d) Precisa-se demonstrar que, sob essa hipótese,
1^{2}+2^{2}+\cdots+k^{2}+(k+1)^{2} =\frac{(k+1)(k+2)(2k+3)}{6}.

Exercícios de Livros Relacionados