Como você provaria que \(1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}\) para todo número natural \(n\)? Verificar caso a caso é impossível: os naturais são infinitos. Precisamos de um argumento que cubra todos de uma vez.
Essa é a função do Princípio de Indução Matemática — uma das ferramentas de prova mais elegantes da matemática.
Por que a indução matemática? #
A indução aparece sempre que queremos afirmar algo sobre todos os números naturais ao mesmo tempo. Em matemática discreta e ciência da computação, isso acontece com frequência:
- Fórmulas de somas e produtos — calcular a soma de uma progressão, o produto de uma sequência ou o número de subconjuntos de um conjunto de \(n\) elementos exige um argumento que cubra todo \(n \geq 1\).
- Análise de algoritmos — complexidade de laços aninhados, somas de séries geométricas e outras fórmulas que aparecem na análise de desempenho são tipicamente provadas por indução.
- Corretude de funções recursivas — uma função recursiva resolve o caso base diretamente e delega o restante a uma chamada menor; provar que ela retorna o resultado correto para todo \(n\) é, estruturalmente, uma prova por indução.
- Invariantes de laço — demonstrar que uma propriedade vale após cada
iteração de um
forouwhiletambém segue a lógica da indução: base (antes da primeira iteração) e passo (de \(k\) para \(k+1\)). - Teoria das linguagens formais — propriedades de gramáticas e autômatos são frequentemente demonstradas por indução estrutural, uma generalização do PIM para estruturas recursivas.
Este artigo apresenta o método e seus exemplos fundamentais. As conexões com programação aparecem ao longo do texto.
A Intuição: Dominós e Escada #
Imagine uma fileira infinita de dominós em pé. Se você sabe que:
- O primeiro dominó cai, e
- Sempre que um dominó cai, o próximo também cai,
então todos os dominós vão cair — mesmo que haja infinitos deles.
A figura abaixo mostra essa fileira com cada dominó rotulado pela afirmação que ele representa: o primeiro já tombou, e cada seta indica que a queda de um dominó derruba o seguinte.
Outra imagem: uma escada infinita. Se você consegue subir no primeiro degrau e, estando em qualquer degrau, sempre consegue subir ao seguinte, então alcança qualquer degrau da escada, por mais alto que esteja. Não é preciso contar os degraus nem subir todos de uma vez: as duas garantias bastam.
A cadeia de implicações resultante se propaga indefinidamente:
flowchart LR P1["P(1)"] --> P2["P(2)"] P2 --> P3["P(3)"] P3 --> P4["P(4)"] P4 --> PN["..."]
Isso é exatamente a lógica da indução matemática.
O Princípio de Indução Matemática #
Seja \(P(n)\) uma propriedade sobre \(n \in \mathbb{N}\). Se:
- Base: \(P(1)\) é verdadeira
- Hipótese indutiva (HI): assume-se que \(P(k)\) é verdadeira para um \(k \geq 1\) fixado arbitrariamente
- Passo indutivo: usando a HI, prova-se que \(P(k+1)\) é verdadeira
Então \(P(n)\) é verdadeira para todo \(n \in \mathbb{N}\).
O PIM é uma técnica central para provar resultados envolvendo números naturais: somas, desigualdades, divisibilidade e propriedades recorrentes.
A ideia é antiga. Provas que usam o método de forma implícita aparecem com o matemático persa al-Karaji, por volta do ano 1000, e o primeiro uso rigoroso é atribuído a Gersonides, no século XIV. Em 1575, Francesco Maurolico usou a técnica para provar que a soma dos \(n\) primeiros ímpares é \(n^2\) — o segundo exemplo deste artigo. A primeira formulação explícita do princípio é de Blaise Pascal, no Traité du triangle arithmétique, publicado em 1665, e o nome “indução matemática” foi dado por Augustus De Morgan em 1838 — o mesmo das leis de De Morgan, vistas no artigo sobre operações entre conjuntos. A história completa está no verbete Mathematical induction.
Não: ele faz parte da própria definição dos números naturais. Nos axiomas de Peano, publicados por Giuseppe Peano em 1889, a indução é um dos axiomas que caracterizam \(\mathbb{N}\) — e Peano, como esta série, começava os naturais em 1. Quem aceita os naturais com essa estrutura aceita, junto, que a indução funciona.
Estrutura de uma Prova por Indução #
Toda prova por indução segue a mesma estrutura em três etapas:
| Etapa | O que fazer |
|---|---|
| 1. Base de indução | Verificar que \(P(1)\) é verdadeira |
| 2. Hipótese indutiva (HI) | Assumir que \(P(k)\) é verdadeira para um \(k \geq 1\) fixado arbitrariamente |
| 3. Passo indutivo | Provar \(P(k+1)\) usando a HI |
Depois de verificar a base e executar o passo indutivo, a conclusão segue automaticamente: \(P(n)\) vale para todo \(n \in \mathbb{N}\).
Exemplos Resolvidos #
Soma dos primeiros \(n\) naturais #
Conta-se que Carl Friedrich Gauss, ainda criança, recebeu do professor a tarefa de somar os números de 1 a 100 e respondeu 5050 em poucos instantes: juntou o primeiro com o último (\(1 + 100\)), o segundo com o penúltimo (\(2 + 99\)), e assim por diante — 50 pares que somam 101 cada. A história é provavelmente apócrifa (veja Gauss’s Day of Reckoning, na American Scientist), mas o truque funciona para qualquer \(n\) e sugere a fórmula; a indução prova que ela vale para todo \(n\).
$$P(n):\ 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$Base (\(n = 1\)): \(1 = \dfrac{1 \cdot 2}{2} = 1\) ✓
HI: \(1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}\)
Passo indutivo (\(n = k+1\)):
$$1 + 2 + \cdots + k + (k+1) \stackrel{\text{HI}}{=} \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}$$Portanto, \(1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}\), que é o que queríamos demonstrar. \(\blacksquare\)
Aplicação: indução e funções recursivas
A prova acima tem uma correspondência direta com a implementação recursiva da soma em Python:
def soma(n):
if n == 1:
return 1
return soma(n - 1) + n
print(soma(100)) # 5050Os três passos da indução mapeiam exatamente para os três elementos da função:
| Indução | Código |
|---|---|
| Base: \(P(1)\) é verdadeira | if n == 1: return 1 |
HI: supõe-se que soma(n-1) retorna \(\frac{(n-1)n}{2}\) |
chamada recursiva soma(n - 1) |
Passo: soma(n-1) + n produz \(\frac{n(n+1)}{2}\) |
return soma(n - 1) + n |
Provar a fórmula por indução é provar que a função recursiva está correta
para todo \(n \in \mathbb{N}\). Toda função recursiva bem formada carrega
implicitamente uma prova por indução. Há ainda uma consequência prática: a
função recursiva e o laço for equivalente executam em \(O(n)\) — o tempo
cresce com \(n\). A fórmula fechada \(\frac{n(n+1)}{2}\) executa em
\(O(1)\), tempo constante. A prova por indução é a garantia matemática de
que essa substituição é segura: os dois lados são equivalentes para todo
\(n\), sem exceção. No artigo sobre
relações de recorrência,
veremos como essa mesma função gera a equação \(S(n) = S(n-1) + n\) e como
resolvê-la formalmente para obter a fórmula fechada.
Soma dos primeiros \(n\) números ímpares #
$$P(n):\ 1 + 3 + 5 + \cdots + (2n - 1) = n^2$$Essa fórmula tem uma beleza geométrica: a soma dos \(n\) primeiros ímpares é sempre um quadrado perfeito. A figura abaixo mostra por quê — cada novo ímpar é um L que completa o quadrado seguinte, que é exatamente o passo \(k^2 + (2k+1) = (k+1)^2\) que a prova faz com álgebra.
Base (\(n = 1\)): \(1 = 1^2\) ✓
HI: \(1 + 3 + \cdots + (2k - 1) = k^2\)
Passo indutivo (\(n = k+1\)):
$$1 + 3 + \cdots + (2k-1) + (2(k+1)-1) \stackrel{\text{HI}}{=} k^2 + 2k + 1 = (k+1)^2$$Portanto, \(1 + 3 + \cdots + (2n-1) = n^2\), que é o que queríamos demonstrar. \(\blacksquare\)
Divisibilidade #
$$P(n):\ 8 \mid (3^{2n} - 1)$$Base (\(n = 1\)): \(3^2 - 1 = 8\), e \(8 \mid 8\) ✓
HI: \(8 \mid (3^{2k} - 1)\), isto é, \(3^{2k} - 1 = 8m\) para algum \(m \in \mathbb{Z}\)
Passo indutivo (\(n = k+1\)):
Queremos mostrar que \(8 \mid (3^{2(k+1)} - 1)\). Primeiro, abrimos o expoente:
$$3^{2(k+1)} - 1 = 3^{2k+2} - 1 = 3^2 \cdot 3^{2k} - 1 = 9 \cdot 3^{2k} - 1$$Agora reescrevemos para isolar \(3^{2k} - 1\), que aparece na HI:
$$9 \cdot 3^{2k} - 1 = 9 \cdot 3^{2k} - 9 + 8 = 9(3^{2k} - 1) + 8$$Pela HI, \(3^{2k} - 1 = 8m\) para algum \(m \in \mathbb{Z}\), logo:
$$9(3^{2k} - 1) + 8 = 9 \cdot 8m + 8 = 8(9m + 1)$$Portanto, \(8 \mid (3^{2n} - 1)\), que é o que queríamos demonstrar. \(\blacksquare\)
Aplicação: invariantes de laço
A mesma lógica da indução garante a corretude de laços iterativos. Considere
o for abaixo, que computa a soma acumulada:
n = 100
total = 0
for k in range(1, n + 1):
total += k
print(total == n * (n + 1) // 2) # TrueDefina o invariante \(P(k)\): “após a \(k\)-ésima iteração,
total == k*(k+1)//2”. Então:
- Base (\(k = 0\), antes do laço):
total = 0e \(0 \cdot 1 / 2 = 0\) ✓ - Passo (de \(k\) para \(k+1\)): se
total == k*(k+1)//2antes da iteração \(k+1\), então apóstotal += k+1temos \(\frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}\) ✓
Ao fim do laço, \(k = n\), portanto total == n*(n+1)//2. Esse argumento é
indução disfarçada — e é exatamente o mecanismo que verificadores formais
(como os baseados em Lógica de Hoare) usam para provar corretude de programas
iterativos.
PIM Generalizado: Base em \(n_0 \neq 1\) #
Nem toda propriedade vale a partir de \(n = 1\). Quando queremos provar \(P(n)\) para todo \(n \geq n_0\), usamos a versão generalizada:
Para provar \(P(n)\) para todo \(n \geq n_0\):
- Base: verificar que \(P(n_0)\) é verdadeira
- Hipótese indutiva (HI): assumir que \(P(k)\) é verdadeira para um \(k \geq n_0\) fixado arbitrariamente
- Passo indutivo: usando a HI, provar que \(P(k+1)\) é verdadeira
Quando \(n_0 = 1\), obtemos o PIM usual como caso particular.
Exemplo: \(n^2 > 3n\) para \(n \geq 4\) #
A propriedade \(n^2 > 3n\) não vale para \(n = 1, 2, 3\):
- \(1^2 = 1 \not> 3\)
- \(2^2 = 4 \not> 6\)
- \(3^2 = 9 \not> 9\)
A indução só pode começar em \(n_0 = 4\).
Base (\(n = 4\)): \(16 > 12\) ✓
HI: \(k^2 > 3k\) para algum \(k \geq 4\)
Passo indutivo (\(n = k+1\)):
$$(k+1)^2 = k^2 + 2k + 1 \stackrel{\text{HI}}{>} 3k + 2k + 1 = 5k + 1 > 3(k+1) = 3k + 3$$(válido pois \(5k + 1 > 3k + 3 \iff 2k > 2 \iff k > 1\), que é verdade para \(k \geq 4\))
Portanto, \(n^2 > 3n\), que é o que queríamos demonstrar. \(\blacksquare\)
Quando a Indução Falha #
O método é tão confiável quanto cada uma de suas partes. Um exemplo famoso mostra o que acontece quando o passo indutivo tem um furo: num artigo satírico de 1961, o matemático Joel E. Cohen “provou” que todos os cavalos têm a mesma cor.
$$P(n):\ \text{em qualquer grupo de } n \text{ cavalos, todos têm a mesma cor}$$Base (\(n = 1\)): um grupo de um só cavalo tem uma só cor ✓
HI: em qualquer grupo de \(k\) cavalos, todos têm a mesma cor.
“Passo indutivo” (\(n = k+1\)): numere os cavalos de um grupo de \(k+1\) de 1 a \(k+1\). Sem o último, sobram os cavalos de 1 a \(k\), que pela HI têm a mesma cor. Sem o primeiro, sobram os cavalos de 2 a \(k+1\), que pela HI também têm a mesma cor. Como os dois grupos têm cavalos em comum, as duas cores são uma só, e os \(k+1\) cavalos têm todos a mesma cor.
A base está certa, e o argumento do passo funciona para \(k \geq 2\). O furo está em \(k = 1\): num grupo de 2 cavalos, “os cavalos de 1 a \(k\)” é só o cavalo 1 e “os de 2 a \(k+1\)” é só o cavalo 2 — não há cavalo em comum, e nada liga as duas cores. A implicação \(P(1) \Rightarrow P(2)\) nunca foi provada: o primeiro dominó cai, mas nada garante que ele derrube o segundo. O passo indutivo precisa valer para todo \(k \geq n_0\), inclusive o primeiro — justamente onde esse argumento quebra. Mais em All horses are the same color.
Exercícios #
Pratique aplicando a estrutura das três etapas vista acima. As demonstrações estão disponíveis para conferência após sua tentativa.
Exercício 1 — Soma de potências de 2
Prove por indução que \(1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1\) para todo \(n \in \mathbb{N}\).
Demonstração:
Base (\(n=1\)): \(1 = 2^1 - 1\) ✓
HI: \(1 + 2 + \cdots + 2^{k-1} = 2^k - 1\)
Passo indutivo:
$$1 + 2 + \cdots + 2^{k-1} + 2^k \stackrel{\text{HI}}{=} (2^k - 1) + 2^k = 2 \cdot 2^k - 1 = 2^{k+1} - 1$$Portanto, \(1 + 2 + \cdots + 2^{n-1} = 2^n - 1\), que é o que queríamos demonstrar. \(\blacksquare\)
Exercício 2 — Soma dos quadrados
Prove que \(1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}\) para todo \(n \in \mathbb{N}\).
Demonstração:
Base (\(n=1\)): \(1 = \dfrac{1 \cdot 2 \cdot 3}{6} = 1\) ✓
HI: \(1^2 + 2^2 + \cdots + k^2 = \dfrac{k(k+1)(2k+1)}{6}\)
Passo indutivo:
$$1^2 + \cdots + k^2 + (k+1)^2 \stackrel{\text{HI}}{=} \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\left(\frac{k(2k+1)}{6} + (k+1)\right)$$$$= (k+1) \cdot \frac{2k^2+7k+6}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$$Portanto, \(1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}\), que é o que queríamos demonstrar. \(\blacksquare\)
Exercício 3 — Soma de produtos consecutivos
Prove que \(\displaystyle\sum_{i=1}^{n} i(i+1) = \dfrac{n(n+1)(n+2)}{3}\) para todo \(n \in \mathbb{N}\).
Demonstração:
Base (\(n=1\)): \(1 \cdot 2 = 2\) e \(\dfrac{1 \cdot 2 \cdot 3}{3} = 2\) ✓
HI: \(\displaystyle\sum_{i=1}^{k} i(i+1) = \dfrac{k(k+1)(k+2)}{3}\)
Passo indutivo:
$$\sum_{i=1}^{k+1} i(i+1) \stackrel{\text{HI}}{=} \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) = (k+1)(k+2)\left(\frac{k}{3}+1\right) = \frac{(k+1)(k+2)(k+3)}{3}$$Portanto, \(\displaystyle\sum_{i=1}^{n} i(i+1) = \dfrac{n(n+1)(n+2)}{3}\), que é o que queríamos demonstrar. \(\blacksquare\)
Exercício 4 — Progressão aritmética
Prove que \(2 + 5 + 8 + \cdots + (3n-1) = \dfrac{n(1+3n)}{2}\) para todo \(n \in \mathbb{N}\).
Demonstração:
Base (\(n=1\)): \(3(1)-1 = 2\) e \(\dfrac{1 \cdot 4}{2} = 2\) ✓
HI: \(\displaystyle\sum_{i=1}^{k}(3i-1) = \dfrac{k(1+3k)}{2}\)
Passo indutivo:
$$\sum_{i=1}^{k+1}(3i-1) \stackrel{\text{HI}}{=} \frac{k(1+3k)}{2} + (3k+2) = \frac{k+3k^2+6k+4}{2} = \frac{3k^2+7k+4}{2} = \frac{(k+1)(3k+4)}{2}$$Portanto, \(2 + 5 + \cdots + (3n-1) = \dfrac{n(1+3n)}{2}\), que é o que queríamos demonstrar. \(\blacksquare\)
Exercício 5 — Produto telescópico
Prove que \(\left(1+1\right)\left(1+\dfrac{1}{2}\right)\left(1+\dfrac{1}{3}\right)\cdots\left(1+\dfrac{1}{n}\right) = n+1\) para todo \(n \in \mathbb{N}\).
Demonstração:
Base (\(n=1\)): \(1 + \dfrac{1}{1} = 2 = 1+1\) ✓
HI: \(\displaystyle\prod_{i=1}^{k}\left(1+\dfrac{1}{i}\right) = k+1\)
Passo indutivo:
$$\prod_{i=1}^{k+1}\left(1+\frac{1}{i}\right) \stackrel{\text{HI}}{=} (k+1)\left(1+\frac{1}{k+1}\right) = (k+1)\cdot\frac{k+2}{k+1} = k+2$$Portanto, \(\displaystyle\prod_{i=1}^{n}\left(1+\dfrac{1}{i}\right) = n+1\), que é o que queríamos demonstrar. \(\blacksquare\)
Exercício 6 — Divisibilidade
Prove que \(2 \mid n^2 + n\) para todo \(n \in \mathbb{N}\).
Demonstração:
Base (\(n=1\)): \(1+1 = 2\), divisível por 2 ✓
HI: \(k^2 + k = 2q\) para algum \(q \in \mathbb{N}\)
Passo indutivo:
$$(k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = \underbrace{(k^2+k)}_{2q} + 2(k+1) = 2\bigl(q + k + 1\bigr)$$Portanto, \(2 \mid n^2 + n\), que é o que queríamos demonstrar. \(\blacksquare\)
Observação: A fatoração \(n^2 + n = n(n+1)\) revela a intuição — produto de inteiros consecutivos, um deles sempre par — mas é a indução que formaliza a prova para todos os naturais.
Tabela-Resumo #
Os resultados provados neste artigo, reunidos para consulta rápida:
| Resultado | Enunciado |
|---|---|
| Soma dos naturais | \(1+2+\cdots+n = \dfrac{n(n+1)}{2}\) |
| Soma dos ímpares | \(1+3+\cdots+(2n-1) = n^2\) |
| Divisibilidade | \(8 \mid (3^{2n}-1)\) |
| Desigualdade (\(n \geq 4\)) | \(n^2 > 3n\) |
| Potências de 2 | \(1+2+\cdots+2^{n-1} = 2^n - 1\) |
| Soma dos quadrados | \(1^2+2^2+\cdots+n^2 = \dfrac{n(n+1)(2n+1)}{6}\) |
| Soma de produtos consecutivos | \(\displaystyle\sum_{i=1}^{n} i(i+1) = \dfrac{n(n+1)(n+2)}{3}\) |
| Progressão aritmética | \(2+5+\cdots+(3n-1) = \dfrac{n(1+3n)}{2}\) |
| Produto telescópico | \(\displaystyle\prod_{i=1}^{n}\left(1+\frac{1}{i}\right) = n+1\) |
| Divisibilidade simples | \(2 \mid n^2+n\) |
Próximos passos #
O PIM padrão usa apenas o caso \(P(k)\) para provar \(P(k+1)\). Mas alguns problemas exigem todos os casos anteriores ao mesmo tempo. Considere, por exemplo, provar que todo inteiro \(n \geq 2\) admite um fator primo: para decompor \(n\), pode ser necessário invocar a hipótese para valores menores que \(k\), não só para \(k\). O PIM padrão não alcança esse argumento — e para isso existe a Indução Forte, tema do próximo artigo.
