No artigo anterior, o Princípio de Indução Matemática (PIM) assumia apenas \(P(k)\) para provar \(P(k+1)\). Isso é suficiente em muitos casos. Mas e quando o passo \(k+1\) depende não apenas de \(k\), mas de dois ou mais casos anteriores ao mesmo tempo?
A resposta é a Indução Forte — uma variante que assume a verdade de todos os casos anteriores de uma vez.
Por que a Indução Forte? #
A indução simples basta quando cada passo depende apenas do caso imediatamente anterior. A indução forte é necessária quando o raciocínio precisa recuar mais de um nível — o que acontece com frequência em ciência da computação:
- Sequências recorrentes de múltiplos passos — Fibonacci usa \(F_{k+1} = F_k + F_{k-1}\); provar qualquer propriedade desse tipo de sequência por indução exige ambos os casos anteriores.
- Algoritmos de divisão e conquista — Merge sort e quick sort dividem o problema em partes de tamanho arbitrário (não necessariamente \(k-1\)); a prova de corretude precisa da hipótese para todos os subproblemas menores.
- Fatoração e teoria dos números — a prova de que todo inteiro \(n > 1\) tem um fator primo requer a hipótese para qualquer divisor de \(n\), que pode ser bem menor que \(n-1\).
- Propriedades estruturais de árvores — demonstrações sobre uma árvore de \(n\) nós frequentemente recaem em subárvores de tamanho qualquer menor que \(n\).
Este artigo apresenta a técnica com exemplos de crescente complexidade, culminando na Fórmula de Binet para Fibonacci.
A Sequência de Fibonacci #
Antes do princípio formal, vale apresentar a sequência que será usada como exemplo ao longo deste artigo.
Primeiros termos: \(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\)
Cada termo é a soma dos dois anteriores:
$$F_3 = F_2 + F_1 = 2, \quad F_4 = F_3 + F_2 = 3, \quad F_5 = F_4 + F_3 = 5, \ldots$$Uma identidade observada #
Calculando os primeiros casos:
| \(n\) | \(F_1^2 + \cdots + F_n^2\) | \(F_n \cdot F_{n+1}\) |
|---|---|---|
| 1 | 1 | \(1 \cdot 1 = 1\) |
| 2 | 2 | \(1 \cdot 2 = 2\) |
| 3 | 6 | \(2 \cdot 3 = 6\) |
| 4 | 15 | \(3 \cdot 5 = 15\) |
O padrão sugere: \(F_1^2 + F_2^2 + \cdots + F_n^2 = F_n \cdot F_{n+1}\).
Essa identidade pode ser provada por indução simples (cada passo só precisa do caso anterior):
Base (\(n = 1\)): \(F_1^2 = 1 = F_1 \cdot F_2\) ✓
HI: \(F_1^2 + \cdots + F_k^2 = F_k \cdot F_{k+1}\)
Passo indutivo (\(n = k+1\)):
$$F_1^2 + \cdots + F_k^2 + F_{k+1}^2 \stackrel{\text{HI}}{=} F_k F_{k+1} + F_{k+1}^2 = F_{k+1}(F_k + F_{k+1}) = F_{k+1} \cdot F_{k+2}$$Portanto, \(F_1^2 + F_2^2 + \cdots + F_n^2 = F_n \cdot F_{n+1}\), que é o que queríamos demonstrar. \(\blacksquare\)
Aplicação: Fibonacci recursivo e complexidade exponencial
A implementação recursiva ingênua de Fibonacci em Python espelha diretamente a definição:
def fib(n):
if n <= 2:
return 1
return fib(n - 1) + fib(n - 2)Cada chamada gera duas chamadas menores — fib(n-1) e fib(n-2) — e muitos
subproblemas são recalculados repetidamente. O Exemplo 1 prova por indução forte que
\(F_n < \left(\frac{7}{4}\right)^n\), confirmando que o algoritmo tem complexidade
exponencial — para \(n = 50\), isso representa bilhões de chamadas.
A solução é memoização: armazenar cada \(F_k\) calculado e reutilizá-lo:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 2:
return 1
return fib(n - 1) + fib(n - 2)Com memoização, cada valor é calculado uma única vez — complexidade \(O(n)\).
O impacto de complexidade fica claro em medições práticas. Em uma máquina moderna, para \(n = 30\):
| Versão | Tempo (1 execução) | Complexidade |
|---|---|---|
| Ingênua | ~1–3 s | exponencial |
| Memoizada | < 0,1 ms | \(O(n)\) |
| Binet | < 0,1 ms | \(O(1)\) |
A Fórmula de Binet, que será provada adiante no Exercício 4, reduz o cálculo a \(O(1)\) operações aritméticas, e a indução forte é a garantia matemática de que essa fórmula está correta para todo \(n\).
A redundância de cálculos fica evidente na árvore de chamadas de fib(5): fib(3)
é calculado duas vezes e fib(2) três vezes — e o problema se agrava exponencialmente
com \(n\).
flowchart TD F5["fib(5)"] --> F4["fib(4)"] F5 --> F3a["fib(3)"] F4 --> F3b["fib(3)"] F4 --> F2a["fib(2)"] F3a --> F2b["fib(2)"] F3a --> F1a["fib(1)"] F3b --> F2c["fib(2)"] F3b --> F1b["fib(1)"]
Princípio de Indução Forte #
Seja \(P(n)\) uma propriedade sobre \(n \in \mathbb{N}\). Se:
- Base: \(P(1)\) é verdadeira
- Passo: \(\bigl[P(1), P(2), \ldots, P(k)\ \text{são todas verdadeiras}\bigr] \Rightarrow P(k+1)\)
Então \(P(n)\) é verdadeira para todo \(n \in \mathbb{N}\).
O Princípio de Indução Forte é equivalente ao PIM padrão: qualquer proposição que pode ser provada por um também pode ser provada pelo outro. A diferença é prática: a hipótese mais forte da indução forte torna certas provas muito mais diretas.
A diferença está na hipótese: no PIM, assumimos apenas \(P(k)\). Na indução forte, assumimos \(P(1), P(2), \ldots, P(k)\) — todos os casos anteriores simultaneamente. Isso é particularmente útil quando \(P(k+1)\) depende de casos mais distantes (como \(P(k-1)\), \(P(k-2)\), etc.).
O diagrama abaixo contrasta as duas cadeias de implicação: na indução simples, cada nó recebe seta apenas do anterior; na indução forte, cada nó recebe setas de todos os anteriores.
flowchart LR
subgraph simples["Indução Simples"]
direction LR
P1["P(1)"] --> P2["P(2)"]
P2 --> P3["P(3)"]
P3 --> P4["P(4)"]
P4 --> PN["..."]
end
subgraph forte["Indução Forte"]
direction LR
Q1["P(1)"] --> Q3["P(3)"]
Q2["P(2)"] --> Q3
Q1 --> Q4["P(4)"]
Q2 --> Q4
Q3 --> Q4
Q4 --> QN["..."]
end
Estrutura da prova #
Toda prova por indução forte segue a mesma estrutura em três etapas:
| Etapa | O que fazer |
|---|---|
| Base | Verificar \(P(1)\) (e às vezes \(P(2)\) ou mais) |
| Hipótese forte (HIF) | Assumir \(P(1), P(2), \ldots, P(k)\) verdadeiras para um \(k \geq 1\) fixado arbitrariamente |
| Passo indutivo | Provar \(P(k+1)\) usando a HIF |
Quando a recorrência no passo indutivo recua \(r\) posições — isto é, \(P(k+1)\) depende de \(P(k), P(k-1), \ldots, P(k-r+1)\) — é preciso verificar \(r\) casos base independentemente. Para Fibonacci (\(r = 2\)), os casos \(P(1)\) e \(P(2)\) são necessários; para uma recorrência de ordem 3, seriam \(P(1)\), \(P(2)\) e \(P(3)\). Sem esses casos iniciais, a cadeia indutiva não tem ponto de partida suficiente.
Aplicação: Merge sort e corretude por divisão e conquista
O merge sort ordena uma lista dividindo-a ao meio, ordenando cada metade recursivamente e fundindo os resultados:
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
return result + a[i:] + b[j:]
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)A prova de corretude segue exatamente a estrutura da indução forte:
| Etapa | No merge sort |
|---|---|
| Base | len(lst) <= 1 — lista vazia ou unitária já está ordenada |
| HIF | merge_sort(lst[:mid]) e merge_sort(lst[mid:]) retornam listas ordenadas (subproblemas de tamanhos \(\lfloor n/2 \rfloor\) e \(\lceil n/2 \rceil\), ambos \(\leq k\)) |
| Passo | merge(left, right) — fusão de duas listas ordenadas produz lista ordenada |
A indução simples não bastaria aqui: os subproblemas têm tamanhos \(\lfloor n/2 \rfloor\) e \(\lceil n/2 \rceil\) — não necessariamente \(n-1\). A HIF garante a corretude para qualquer tamanho de subproblema menor que \(n\).
A árvore de chamadas de merge_sort([5, 3, 8, 1]) contrasta com a do Fibonacci:
cada subproblema é calculado uma única vez e os resultados são combinados de
baixo para cima pelas fusões.
flowchart TD A["[5, 3, 8, 1]"] -->|divide| B["[5, 3]"] A -->|divide| C["[8, 1]"] B -->|divide| D["[5]"] B -->|divide| E["[3]"] C -->|divide| F["[8]"] C -->|divide| G["[1]"] D & E -->|merge| H["[3, 5]"] F & G -->|merge| I["[1, 8]"] H & I -->|merge| J["[1, 3, 5, 8] ✓"]
Exemplo 1: \(F_n < \left(\frac{7}{4}\right)^n\) #
Esse resultado não pode ser provado com indução simples porque \(F_{k+1} = F_k + F_{k-1}\) depende de dois casos anteriores.
Base: \(P(1)\): \(F_1 = 1 < \dfrac{7}{4}\) ✓ \(P(2)\): \(F_2 = 1 < \left(\dfrac{7}{4}\right)^2 = \dfrac{49}{16}\) ✓
HIF: \(F_j < \left(\dfrac{7}{4}\right)^j\) para \(j = 1, 2, \ldots, k\).
Passo indutivo (\(n = k+1\), com \(k \geq 2\)):
$$F_{k+1} = F_k + F_{k-1} \stackrel{\text{HIF}}{<} \left(\frac{7}{4}\right)^k + \left(\frac{7}{4}\right)^{k-1} = \left(\frac{7}{4}\right)^{k-1}\left(\frac{7}{4} + 1\right) = \left(\frac{7}{4}\right)^{k-1} \cdot \frac{11}{4}$$Como \(\dfrac{11}{4} < \left(\dfrac{7}{4}\right)^2 = \dfrac{49}{16}\):
$$F_{k+1} < \left(\frac{7}{4}\right)^{k-1} \cdot \left(\frac{7}{4}\right)^2 = \left(\frac{7}{4}\right)^{k+1}$$Portanto, \(F_n < \left(\dfrac{7}{4}\right)^n\), que é o que queríamos demonstrar. \(\blacksquare\)
Indução Forte Generalizada (base em \(n_0\)) #
Assim como o PIM tem versão generalizada, a indução forte também:
Para provar \(P(n)\) para todo \(n \geq n_0\):
- Base: verificar \(P(n_0)\)
- Hipótese: \(P(n_0), P(n_0+1), \ldots, P(k)\) são verdadeiras
- Passo: provar \(P(k+1)\)
Exemplo 2: Decomposição em Primos #
O Exemplo 2 aplica a variante generalizada com \(n_0 = 2\): o enunciado vale para todo \(n > 1\), e não há inteiros maiores que 1 e menores que 2 para verificar antes do caso base.
Todo inteiro \(n > 1\) é primo ou pode ser escrito como produto de números primos.
Base (\(n = 2\)): \(2\) é primo ✓
HIF: \(P(2), P(3), \ldots, P(k)\) são verdadeiras.
Passo (\(n = k+1\)):
- Se \(k+1\) é primo, \(P(k+1)\) é verdadeira.
- Se \(k+1\) não é primo, então \(k+1 = a \cdot b\) com \(2 \leq a, b < k+1\).
- Pela HIF, \(a\) e \(b\) são primos ou produtos de primos.
- Logo \(k+1 = a \cdot b\) também é produto de primos.
Portanto, todo inteiro \(n > 1\) é primo ou produto de primos, que é o que queríamos demonstrar. \(\blacksquare\)
Por que esse exemplo requer a indução forte? Porque quando \(k+1\) se decompõe como \(a \cdot b\), não há garantia de que \(a\) ou \(b\) seja igual a \(k\). Pode ser qualquer valor entre 2 e \(k-1\). A indução simples, que só garante \(P(k)\), não é suficiente.
Exemplo 3: A Barra de Chocolate #
Uma barra de chocolate \(m \times n\) quadradinhos pode ser partida em quadradinhos individuais em muitas ordens diferentes. Quantas quebras são necessárias no total?
Seja \(Q(k)\): “partir um pedaço de \(k\) quadradinhos em unidades requer exatamente \(k-1\) quebras.” Provamos \(Q(k)\) por indução forte em \(k\).
Base (\(k=1\)): um quadradinho já está partido; \(0 = 1-1\) quebras. ✓
HIF: \(Q(j)\) é verdadeira para todo \(j = 1, 2, \ldots, k\).
Passo indutivo (\(k+1\) quadradinhos):
A primeira quebra divide o pedaço em duas partes de tamanhos \(a\) e \(b\), com \(a + b = k+1\) e \(1 \leq a, b \leq k\). Pela HIF, a parte de \(a\) quadradinhos precisa de \(a-1\) quebras e a de \(b\) precisa de \(b-1\). O total é:
$$1 + (a-1) + (b-1) = a + b - 1 = k$$Portanto, uma barra \(m \times n\) precisa de exatamente \(mn - 1\) quebras, qualquer que seja a ordem. \(\blacksquare\)
A indução forte é indispensável aqui: ao partir \(k+1\) quadradinhos, os tamanhos \(a\) e \(b\) podem ser quaisquer valores entre 1 e \(k\) — não necessariamente \(k\). A HIF garante a corretude para todos esses casos de uma só vez.
Comparativo: Indução Simples vs. Indução Forte #
| Característica | Indução Simples | Indução Forte |
|---|---|---|
| Hipótese | \(P(k)\) é verdadeira | \(P(1), \ldots, P(k)\) são verdadeiras |
| Passo | \(P(k) \Rightarrow P(k+1)\) | \(P(1) \wedge \cdots \wedge P(k) \Rightarrow P(k+1)\) |
| Quando usar | Próximo passo depende só de \(k\) | Próximo passo depende de múltiplos casos |
| Equivalência | Sim, são equivalentes | Sim, são equivalentes |
Exercícios #
Pratique aplicando a estrutura da indução forte. Os exercícios 1 e 2 são de dificuldade intermediária; os exercícios 3 e 4 exigem mais elaboração algébrica; o exercício 5 é um resultado fundamental em ciência da computação.
Exercício 1 — Cota para Fibonacci
Prove por indução forte que \(F_n \leq 2^{n-1}\) para todo \(n \geq 1\).
Demonstração:
Base (\(n=1\)): \(F_1 = 1 = 2^0\) ✓ Base (\(n=2\)): \(F_2 = 1 \leq 2^1 = 2\) ✓
HIF: \(F_j \leq 2^{j-1}\) para todo \(j = 1, 2, \ldots, k\) com \(k \geq 2\).
Passo indutivo (\(n = k+1\)):
$$F_{k+1} = F_k + F_{k-1} \stackrel{\text{HIF}}{\leq} 2^{k-1} + 2^{k-2} = 3 \cdot 2^{k-2} \leq 4 \cdot 2^{k-2} = 2^k$$Portanto, \(F_n \leq 2^{n-1}\), que é o que queríamos demonstrar. \(\blacksquare\)
Exercício 2 — Franqueio postal
Prove por indução forte que qualquer valor \(n \geq 8\) centavos pode ser pago exatamente usando selos de 3 e 5 centavos.
Demonstração:
Base (\(n=8\)): \(8 = 3 + 5\) ✓ Base (\(n=9\)): \(9 = 3 + 3 + 3\) ✓ Base (\(n=10\)): \(10 = 5 + 5\) ✓
HIF: todo valor \(j\) com \(8 \leq j \leq k\) pode ser pago, para algum \(k \geq 10\).
Passo indutivo (\(n = k+1 \geq 11\)):
Como \(k+1 \geq 11\), temos \((k+1) - 3 = k-2 \geq 8\). Pela HIF, \(k-2\) centavos podem ser pagos com selos de 3 e 5. Acrescentando um selo de 3 centavos, obtemos \((k-2)+3 = k+1\) centavos.
Portanto, todo valor \(n \geq 8\) centavos pode ser pago, que é o que queríamos demonstrar. \(\blacksquare\)
O enunciado começa em 8 porque 7 é o maior valor que não pode ser representado com selos de 3 e 5 centavos — não por acidente, mas pelo Problema de Frobenius: dados dois inteiros coprimos \(a\) e \(b\), o maior valor irrepresentável é \(ab - a - b\). Para \(a=3, b=5\): \(15 - 3 - 5 = 7\). O resultado foi publicado por Sylvester em 1884 e generalizado por Frobenius para múltiplos denominadores. Para três ou mais denominadores, o problema permanece em aberto em geral. Veja este artigo para uma visão abrangente.
Exercício 3 — Sequência com dois casos base
Seja \(\{a_n\}\) definida por \(a_1 = 1\), \(a_2 = 5\) e \(a_n = a_{n-1} + 2a_{n-2}\) para \(n \geq 3\). Mostre por indução forte que \(a_n = 2^n + (-1)^n\) para todo \(n \geq 1\).
Demonstração:
Base (\(n=1\)): \(2^1 + (-1)^1 = 1 = a_1\) ✓ Base (\(n=2\)): \(2^2 + (-1)^2 = 5 = a_2\) ✓
HIF: \(a_i = 2^i + (-1)^i\) para todo \(i = 1, 2, \ldots, k\) com \(k \geq 2\).
Passo indutivo (\(n = k+1\)):
$$a_{k+1} = a_k + 2a_{k-1} \stackrel{\text{HIF}}{=} \bigl[2^k + (-1)^k\bigr] + 2\bigl[2^{k-1} + (-1)^{k-1}\bigr]$$$$= 2^k + (-1)^k + 2^k + 2(-1)^{k-1} = 2^{k+1} + (-1)^{k-1}\bigl[(-1) + 2\bigr] = 2^{k+1} + (-1)^{k+1}$$
Portanto, \(a_n = 2^n + (-1)^n\), que é o que queríamos demonstrar. \(\blacksquare\)
A expressão do Exercício 4 foi descoberta por Abraham de Moivre em 1718 — mais de um século antes de Jacques Binet publicá-la em 1843. O nome ficou errado por uma cadeia de publicações secundárias que citavam Binet sem verificar a origem (veja a seção histórica na Wikipedia). É um caso clássico da Lei de Stigler: “nenhuma descoberta científica leva o nome de quem a descobriu de fato.”
Exercício 4 — Fórmula de Binet para Fibonacci
A Fórmula de Binet dá o \(n\)-ésimo termo de Fibonacci diretamente:
$$F_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$$Prove essa fórmula por indução forte.
Demonstração: Seja \(\varphi = \dfrac{1+\sqrt{5}}{2}\) e \(\psi = \dfrac{1-\sqrt{5}}{2}\) (\(\varphi\) é a razão áurea).
Base (\(n=1\)): \(\dfrac{1}{\sqrt{5}}(\varphi - \psi) = \dfrac{1}{\sqrt{5}} \cdot \sqrt{5} = 1 = F_1\) ✓ Base (\(n=2\)): \(\dfrac{1}{\sqrt{5}}(\varphi^2 - \psi^2) = \dfrac{1}{\sqrt{5}}(\varphi+\psi)(\varphi-\psi) = \dfrac{1}{\sqrt{5}} \cdot 1 \cdot \sqrt{5} = 1 = F_2\) ✓
HIF: \(F_i = \dfrac{\varphi^i - \psi^i}{\sqrt{5}}\) para todo \(i = 1, 2, \ldots, k\) com \(k \geq 2\).
Passo indutivo (\(n = k+1\)):
$$F_{k+1} = F_k + F_{k-1} \stackrel{\text{HIF}}{=} \frac{\varphi^k - \psi^k}{\sqrt{5}} + \frac{\varphi^{k-1} - \psi^{k-1}}{\sqrt{5}} = \frac{\varphi^{k-1}(\varphi+1) - \psi^{k-1}(\psi+1)}{\sqrt{5}}$$Como \(\varphi^2 = \varphi + 1\) e \(\psi^2 = \psi + 1\) (propriedade da razão áurea):
$$F_{k+1} = \frac{\varphi^{k-1} \cdot \varphi^2 - \psi^{k-1} \cdot \psi^2}{\sqrt{5}} = \frac{\varphi^{k+1} - \psi^{k+1}}{\sqrt{5}}$$Portanto, \(F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}}\), que é o que queríamos demonstrar. \(\blacksquare\)
Exercício 5 — Representação binária
Prove por indução forte que todo inteiro \(n \geq 1\) pode ser escrito como soma de potências distintas de 2 (representação binária).
Demonstração:
Base (\(n=1\)): \(1 = 2^0\). ✓
HIF: todo inteiro \(j\) com \(1 \leq j \leq k\) tem representação binária.
Passo indutivo (\(n = k+1\)):
- Se \(k+1\) é ímpar: então \(k\) é par. Pela HIF, \(k\) tem representação binária usando somente potências \(2^1, 2^2, \ldots\) (pois \(k\) é par, não contém \(2^0\)). Acrescentando \(2^0\) obtemos representação de \(k+1\) com potências distintas. ✓
- Se \(k+1\) é par: então \(\dfrac{k+1}{2} \leq k\). Pela HIF, \(\dfrac{k+1}{2}\) tem representação binária \(2^{a_1} + \cdots + 2^{a_r}\). Somando 1 a cada expoente (equivalente a multiplicar por 2) obtemos \(k+1 = 2^{a_1+1} + \cdots + 2^{a_r+1}\), com potências distintas. ✓
Portanto, todo inteiro \(n \geq 1\) tem representação binária. \(\blacksquare\)
Tabela-Resumo #
Os resultados provados neste artigo, reunidos para consulta rápida:
| Resultado | Enunciado |
|---|---|
| Identidade de Fibonacci | \(F_1^2 + F_2^2 + \cdots + F_n^2 = F_n \cdot F_{n+1}\) |
| Cota exponencial | \(F_n < \left(\dfrac{7}{4}\right)^n\) |
| Decomposição em primos | Todo \(n > 1\) é primo ou produto de primos |
| Barra de chocolate (Exemplo 3) | Uma barra \(m \times n\) requer exatamente \(mn - 1\) quebras |
| Cota para Fibonacci (Ex. 1) | \(F_n \leq 2^{n-1}\) |
| Franqueio postal (Ex. 2) | Todo \(n \geq 8\) centavos pode ser pago com selos de 3 e 5 centavos |
| Sequência recorrente (Ex. 3) | \(a_n = 2^n + (-1)^n\) onde \(a_n = a_{n-1} + 2a_{n-2}\) |
| Fórmula de Binet (Ex. 4) | \(F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}}\) com \(\varphi = \dfrac{1+\sqrt{5}}{2}\) |
| Representação binária (Ex. 5) | Todo inteiro \(n \geq 1\) tem representação em base 2 |
Próximos passos #
A recorrência de Fibonacci é um exemplo de relação de recorrência — uma fórmula que define cada termo a partir de termos anteriores. O próximo artigo generaliza essa ideia, apresentando técnicas sistemáticas para resolver esse tipo de equação.
Até lá!
