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 Lâmpadas #
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.
Outra imagem: uma fileira infinita de lâmpadas conectadas em série. Acender a primeira lâmpada acende a seguinte, que acende a próxima, e assim por diante. A garantia de que a primeira acende, combinada com a garantia de que cada lâmpada acende a próxima, é suficiente para que todas acendam.
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.
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 #
$$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) + nOs 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.
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:
total = 0
for k in range(1, n + 1):
total += k
# ao final: total == n*(n+1)//2Defina 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\)
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 \overset{\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 \overset{\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) \overset{\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) \overset{\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) \overset{\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.
