Indução Matemática — Princípio, Passos e Exemplos

A indução matemática é um método de demonstração usado para mostrar que uma afirmação é verdadeira para todo inteiro a partir de um certo valor inicial. Para provar uma afirmação para todo $n \ge n_0$, você mostra que o primeiro caso é verdadeiro e depois mostra que a verdade em um inteiro implica a verdade no próximo inteiro.

Se as duas partes estiverem corretas, a afirmação vale para todo inteiro no intervalo indicado. Essa é a ideia central.

Como funciona a indução matemática

Escreva a afirmação como $P(n)$. Então a indução tem esta estrutura:

1. Prove o caso base: mostre que $P(n_0)$ é verdadeiro.
2. Prove o passo indutivo: mostre que, se $P(k)$ é verdadeiro para um inteiro arbitrário $k \ge n_0$, então $P(k+1)$ também é verdadeiro.

Depois de fazer isso, você pode concluir que $P(n)$ é verdadeiro para todo inteiro $n \ge n_0$.

A lógica é sequencial. O caso base inicia a cadeia, e o passo indutivo faz a cadeia avançar um inteiro de cada vez.

Por que o caso base e o passo indutivo são ambos importantes

O caso base fornece a primeira afirmação verdadeira. O passo indutivo diz que a verdade passa de um inteiro para o seguinte.

Assim, se $P(n_0)$ é verdadeiro, então $P(n_0 + 1)$ também é verdadeiro. Depois, $P(n_0 + 2)$ é verdadeiro, e assim por diante. A indução não ignora o ponto de partida, nem ignora a ligação entre um caso e o próximo.

Exemplo resolvido: provando uma fórmula de soma por indução

Um exemplo padrão é a fórmula

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

para todo inteiro $n \ge 1$.

Seja

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Caso base

Tome $n = 1$. O lado esquerdo é $1$, e o lado direito é

$$\frac{1(1+1)}{2} = 1$$

Logo, $P(1)$ é verdadeiro.

Passo indutivo

Suponha que $P(k)$ seja verdadeiro para algum inteiro arbitrário $k \ge 1$. Isso significa que

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Agora prove $P(k+1)$. Comece com o lado esquerdo para $k+1$:

$$1 + 2 + 3 + \cdots + k + (k+1)$$

Usando a hipótese de indução,

$$\frac{k(k+1)}{2} + (k+1)$$

Coloque $(k+1)$ em evidência:

$$(k+1)\left(\frac{k}{2} + 1\right)$$

Depois, simplifique:

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

Essa é exatamente a fórmula com $n = k+1$. Portanto, $P(k+1)$ é verdadeiro.

Como o caso base e o passo indutivo foram ambos provados, a fórmula vale para todo inteiro $n \ge 1$.

Quando usar indução matemática

A indução é útil quando uma afirmação depende de um parâmetro inteiro e cada caso se conecta naturalmente a um anterior. Isso acontece com frequência em somas, afirmações de divisibilidade, desigualdades, relações de recorrência e demonstrações de algoritmos.

Primeiro, identifique o valor inicial correto. Algumas afirmações começam em $n = 0$, outras em $n = 1$, e algumas só fazem sentido para inteiros maiores.

Depois, verifique qual é o próximo caso válido. O passo usual é de $k$ para $k+1$, mas, se a afirmação tratar apenas de inteiros pares, um passo de $k$ para $k+2$ pode ser a versão correta.

Erros comuns em demonstrações por indução

Provar apenas o caso base

O caso base verifica apenas o primeiro valor. Sozinho, ele não prova a afirmação para os inteiros seguintes.

Usar o valor inicial errado

Se a afirmação vale para todo $n \ge 2$, provar apenas $P(1)$ não ajuda. O caso base precisa corresponder ao intervalo real da afirmação.

Tratar a hipótese de indução sem cuidado

No passo indutivo, você supõe $P(k)$ para um inteiro arbitrário $k$ no intervalo válido. Você não supõe que o teorema inteiro já esteja provado.

Provar o próximo caso errado

Se o seu teorema exige um passo de $k \to k+1$, provar um passo diferente não conclui o argumento, a menos que você explique por que esse outro passo é suficiente.

Uma extensão útil: indução forte

Às vezes, provar $P(k+1)$ exige mais do que apenas $P(k)$. Nessa situação, a indução forte permite supor todos os casos anteriores até $k$ e então provar o próximo.

A ideia é muito próxima, mas a suposição é mais forte. Ela é útil, por exemplo, quando uma demonstração depende de dividir um número em partes menores.

Tente sua própria versão

Considere a afirmação

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

e prove-a para todo inteiro $n \ge 1$ usando a mesma estrutura: primeiro o caso base, depois o passo de $k$ para $k+1$. Se você conseguir escrever essa demonstração com clareza, o método geralmente passa a fazer sentido.