O princípio de indução matemática é um dos métodos de demonstração mais importantes de toda a matemática. Permite provar que uma propriedade é válida para todos os números naturais, transformando um problema com infinitos casos num raciocínio finito, rigoroso e controlado.
A ideia de fundo é simples: se uma propriedade é verdadeira no início e se, sempre que é verdadeira para um certo número natural, resulta verdadeira também para o seguinte, então ela é verdadeira para todos os números naturais.
Índice
- Intuição do princípio de indução
- Enunciado do princípio de indução
- Base da indução e passo indutivo
- Por que a indução funciona
- Indução a partir de um valor arbitrário
- Indução e conjuntos indutivos
- Exemplo 1: soma dos primeiros números naturais
- Exemplo 2: uma desigualdade exponencial
- Princípio da boa ordem
- Equivalência entre indução e boa ordem
- Indução forte
- Erros comuns nas demonstrações por indução
- Indução e definições recursivas
- Conclusão
Intuição do princípio de indução
O princípio de indução é frequentemente explicado através da imagem das peças de dominó.
Imaginemos uma fila infinita de peças. Para ter a certeza de que todas caem, não é necessário verificar cada peça individualmente. Basta confirmar dois factos:
- a primeira peça cai;
- cada peça, ao cair, derruba a seguinte.
Se ambas as condições estiverem satisfeitas, então todas as peças da fila cairão.
Em matemática acontece algo análogo. Para demonstrar que uma propriedade \(P(n)\) é válida para todo o número natural \(n\), verifica-se que é válida para o primeiro valor e demonstra-se que a validade para um número qualquer implica a validade para o número seguinte.
Enunciado do princípio de indução
Seja \(P(n)\) uma propriedade dependente de um número natural \(n\). O princípio de indução matemática afirma que, se se verificarem as duas condições:
\[ P(1) \text{ é verdadeira} \]
e
\[ P(n) \Rightarrow P(n+1) \quad \text{para todo o } n \geq 1, \]
então:
\[ P(n) \text{ é verdadeira para todo o } n\in\mathbb{N}, \ n\geq 1. \]
Se, em vez disso, se adoptar a convenção segundo a qual os números naturais começam em \(0\), o caso base será \(P(0)\) e o passo indutivo será:
\[ P(n) \Rightarrow P(n+1) \quad \text{para todo o } n\geq 0. \]
Base da indução e passo indutivo
Uma demonstração por indução é composta por dois momentos fundamentais.
1. Base da indução
Demonstra-se que a propriedade é verdadeira para o primeiro valor considerado, habitualmente \(n=1\) ou \(n=0\).
Esta verificação é indispensável: sem um ponto de partida, a cadeia indutiva não pode começar.
2. Passo indutivo
Supõe-se que a propriedade é verdadeira para um certo número natural \(n\). Esta suposição designa-se por hipótese de indução.
A partir dela, demonstra-se que a propriedade é verdadeira também para \(n+1\).
Em forma simbólica:
\[ P(n)\Rightarrow P(n+1). \]
O ponto essencial é que não se está a assumir que a propriedade é verdadeira para todos os números naturais. Está a demonstrar-se uma implicação: se a propriedade é válida num certo ponto da cadeia, então é válida também no ponto seguinte.
Por que a indução funciona
O princípio de indução funciona porque os números naturais são construídos de forma ordenada e sequencial:
\[ 1,2,3,4,\dots \]
ou, se se partir de \(0\):
\[ 0,1,2,3,\dots \]
Uma vez verificado o primeiro caso, o passo indutivo permite passar do primeiro para o segundo, do segundo para o terceiro, do terceiro para o quarto, e assim sucessivamente.
Gera-se deste modo uma cadeia infinita de implicações:
\[ P(1)\Rightarrow P(2)\Rightarrow P(3)\Rightarrow P(4)\Rightarrow \dots \]
A força da indução reside exactamente aqui: um raciocínio finito consegue controlar infinitos casos porque explora a própria estrutura dos números naturais.
Indução a partir de um valor arbitrário
Não é necessário que a cadeia indutiva parta sempre de \(n=1\) ou de \(n=0\). Em muitas situações, uma propriedade só se torna verdadeira a partir de um certo inteiro \(n_0\).
Neste caso, o princípio de indução enuncia-se da seguinte forma. Se:
\[ P(n_0) \text{ é verdadeira} \]
e
\[ P(n)\Rightarrow P(n+1) \quad \text{para todo o } n\geq n_0, \]
então:
\[ P(n) \text{ é verdadeira para todo o } n\geq n_0. \]
Por exemplo, demonstremos que:
\[ 2^n>n^2 \]
para todo o \(n\geq 5\).
Base da indução
Para \(n=5\), temos:
\[ 2^5=32 \]
e
\[ 5^2=25. \]
Logo:
\[ 2^5>5^2. \]
Passo indutivo
Suponhamos que, para um certo \(n\geq 5\), se verifica:
\[ 2^n>n^2. \]
Temos de demonstrar que:
\[ 2^{n+1}>(n+1)^2. \]
Como:
\[ 2^{n+1}=2\cdot 2^n, \]
usando a hipótese de indução obtemos:
\[ 2^{n+1}=2\cdot 2^n>2n^2. \]
Observemos agora que, para todo o \(n\geq 5\),
\[ 2n^2>(n+1)^2. \]
De facto:
\[ 2n^2-(n+1)^2 = n^2-2n-1. \]
Para \(n\geq 5\), tem-se:
\[ n^2-2n-1=(n-1)^2-2\geq 4^2-2=14>0. \]
Portanto:
\[ 2n^2>(n+1)^2. \]
Combinando as duas desigualdades, obtemos:
\[ 2^{n+1}>2n^2>(n+1)^2. \]
Assim:
\[ 2^{n+1}>(n+1)^2. \]
O passo indutivo está demonstrado. Pelo princípio de indução a partir de \(n_0=5\), concluímos que:
\[ 2^n>n^2 \]
para todo o \(n\geq 5\).
A lógica não muda: a cadeia de implicações começa simplesmente num ponto diferente.
Indução e conjuntos indutivos
O princípio de indução pode também ser enunciado em linguagem conjuntista.
Um subconjunto \(A\subseteq\mathbb{N}\) diz-se indutivo se satisfaz duas condições:
\[ 1\in A \]
e
\[ n\in A\Rightarrow n+1\in A. \]
Por outras palavras, \(A\) contém o primeiro número natural e, juntamente com cada número, contém também o seu sucessor.
O princípio de indução afirma então que:
\[ \text{se } A\subseteq\mathbb{N} \text{ é indutivo, então } A=\mathbb{N}. \]
Esta formulação revela um facto importante: a indução não é apenas uma técnica para resolver exercícios, mas uma propriedade estrutural do conjunto dos números naturais.
Exemplo 1: soma dos primeiros números naturais
Demonstremos por indução que, para todo o \(n\geq 1\),
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2}. \]
Base da indução
Para \(n=1\), o membro esquerdo é:
\[ 1. \]
O membro direito é:
\[ \frac{1(1+1)}{2}=\frac{2}{2}=1. \]
Logo a fórmula é verdadeira para \(n=1\).
Passo indutivo
Suponhamos que a fórmula é verdadeira para um certo \(n\geq 1\), ou seja, suponhamos:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2}. \]
Temos de demonstrar que é então válida também:
\[ 1+2+3+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}. \]
Partimos do membro esquerdo:
\[ 1+2+3+\dots+n+(n+1). \]
Pela hipótese de indução, podemos substituir a soma \(1+2+\dots+n\) por \(\frac{n(n+1)}{2}\):
\[ 1+2+\dots+n+(n+1)=\frac{n(n+1)}{2}+(n+1). \]
Factorizando \(n+1\):
\[ \frac{n(n+1)}{2}+(n+1) = (n+1)\left(\frac{n}{2}+1\right). \]
Como:
\[ \frac{n}{2}+1=\frac{n+2}{2}, \]
obtemos:
\[ (n+1)\left(\frac{n}{2}+1\right) = \frac{(n+1)(n+2)}{2}. \]
Portanto:
\[ 1+2+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}. \]
A propriedade é assim verdadeira para \(n+1\). Pelo princípio de indução, a fórmula é válida para todo o \(n\geq 1\).
Exemplo 2: uma desigualdade exponencial
Demonstremos que, para todo o \(n\in\mathbb{N}\) com \(n\geq 0\),
\[ 2^n\geq n+1. \]
Base da indução
Para \(n=0\), temos:
\[ 2^0=1 \]
e
\[ 0+1=1. \]
Logo:
\[ 2^0\geq 0+1. \]
A propriedade é verdadeira para \(n=0\).
Passo indutivo
Suponhamos que, para um certo \(n\geq 0\), se verifica:
\[ 2^n\geq n+1. \]
Temos de demonstrar que:
\[ 2^{n+1}\geq n+2. \]
Observemos que:
\[ 2^{n+1}=2\cdot 2^n. \]
Usando a hipótese de indução:
\[ 2\cdot 2^n\geq 2(n+1). \]
Logo:
\[ 2^{n+1}\geq 2n+2. \]
Como \(n\geq 0\), temos:
\[ 2n+2\geq n+2. \]
Portanto:
\[ 2^{n+1}\geq n+2. \]
A propriedade é válida também para \(n+1\). Por indução:
\[ 2^n\geq n+1 \]
para todo o \(n\geq 0\).
Princípio da boa ordem
O princípio da boa ordem afirma que todo o subconjunto não vazio de \(\mathbb{N}\) possui um elemento mínimo.
Em símbolos:
\[ A\subseteq\mathbb{N},\quad A\neq\varnothing \quad\Longrightarrow\quad \exists m\in A \text{ tal que } m\leq a \text{ para todo o } a\in A. \]
O elemento \(m\) designa-se por mínimo de \(A\).
Atenção: o mínimo não é simplesmente um elemento pequeno. É um elemento do conjunto que é menor ou igual a todos os outros elementos do conjunto.
Por exemplo, se:
\[ A=\{5,8,13,21\}, \]
então:
\[ \min A=5. \]
Se, por sua vez:
\[ B=\{n\in\mathbb{N}\mid n\geq 10\}, \]
então:
\[ \min B=10. \]
O princípio da boa ordem é uma propriedade característica dos números naturais. Não é válido, por exemplo, para todos os subconjuntos não vazios de \(\mathbb{Z}\). Com efeito, o conjunto:
\[ \mathbb{Z}=\{\dots,-3,-2,-1,0,1,2,3,\dots\} \]
não tem mínimo.
Equivalência entre indução e boa ordem
O princípio de indução e o princípio da boa ordem são equivalentes: admitindo um dos dois, é possível demonstrar o outro.
Esta equivalência é importante porque mostra que a indução não é um simples artifício técnico, mas uma consequência profunda da estrutura ordenada dos números naturais.
Da boa ordem ao princípio de indução
Suponhamos válido o princípio da boa ordem. Queremos demonstrar o princípio de indução.
Seja \(P(n)\) uma propriedade dos números naturais. Suponhamos que:
\[ P(1) \text{ é verdadeira} \]
e que:
\[ P(n)\Rightarrow P(n+1) \quad \text{para todo o } n\geq 1. \]
Queremos demonstrar que \(P(n)\) é verdadeira para todo o \(n\geq 1\).
Raciocinamos por absurdo. Suponhamos que existe pelo menos um número natural para o qual \(P\) é falsa. Consideremos o conjunto dos contraexemplos:
\[ A=\{n\in\mathbb{N}\mid P(n)\text{ é falsa}\}. \]
Por hipótese, \(A\neq\varnothing\). Logo, pelo princípio da boa ordem, \(A\) possui um mínimo. Designemo-lo por \(m\).
Como \(P(1)\) é verdadeira, o número \(1\) não pertence a \(A\). Portanto \(m\neq 1\), o que implica \(m>1\).
Então \(m-1\) é um número natural menor do que \(m\). Como \(m\) é o elemento mínimo de \(A\), o número \(m-1\) não pode pertencer a \(A\).
Logo \(P(m-1)\) é verdadeira.
Mas, pelo passo indutivo:
\[ P(m-1)\Rightarrow P(m). \]
Segue-se que \(P(m)\) é verdadeira.
Isto é impossível, pois \(m\in A\) e, portanto, \(P(m)\) deveria ser falsa.
Obtivemos uma contradição. Logo o conjunto dos contraexemplos é vazio:
\[ A=\varnothing. \]
Portanto \(P(n)\) é verdadeira para todo o \(n\geq 1\). O princípio de indução está demonstrado.
Do princípio de indução à boa ordem
Suponhamos agora válido o princípio de indução. Queremos demonstrar o princípio da boa ordem.
Seja \(A\subseteq\mathbb{N}\) um subconjunto não vazio. Temos de demonstrar que \(A\) possui um mínimo.
Raciocinamos por absurdo. Suponhamos que \(A\) não possui nenhum mínimo.
Se \(1\in A\), então \(1\) seria automaticamente o mínimo de \(A\), uma vez que nenhum número natural positivo é menor do que \(1\). Mas por hipótese \(A\) não tem mínimo. Logo:
\[ 1\notin A. \]
Consideremos agora a propriedade:
\[ P(n): \quad 1,2,\dots,n \notin A. \]
Ou seja, \(P(n)\) afirma que nenhum dos primeiros \(n\) números naturais pertence a \(A\).
Base da indução
Já observámos que:
\[ 1\notin A. \]
Logo \(P(1)\) é verdadeira.
Passo indutivo
Suponhamos verdadeira \(P(n)\), ou seja, suponhamos que:
\[ 1,2,\dots,n \notin A. \]
Temos de demonstrar que:
\[ 1,2,\dots,n,n+1 \notin A. \]
Sabemos já, pela hipótese de indução, que \(1,2,\dots,n\) não pertencem a \(A\). Resta mostrar que \(n+1\notin A\).
Se fosse:
\[ n+1\in A, \]
então \(n+1\) seria o mínimo de \(A\), uma vez que nenhum dos números naturais anteriores pertence a \(A\).
Mas isto contradiz a hipótese de que \(A\) não tem mínimo.
Portanto:
\[ n+1\notin A. \]
O passo indutivo está demonstrado.
Pelo princípio de indução, \(P(n)\) é verdadeira para todo o \(n\geq 1\). Logo nenhum número natural pertence a \(A\), ou seja:
\[ A=\varnothing. \]
Mas isto é impossível, pois tínhamos suposto \(A\neq\varnothing\).
A contradição mostra que \(A\) deve possuir um mínimo. O princípio da boa ordem está demonstrado.
Indução forte
Existe uma variante do princípio de indução denominada indução forte.
Na indução ordinária, para demonstrar \(P(n+1)\), assume-se apenas \(P(n)\).
Na indução forte, por sua vez, para demonstrar \(P(n+1)\), assume-se que são verdadeiras todas as propriedades anteriores:
\[ P(1),P(2),\dots,P(n). \]
O enunciado é o seguinte. Se:
\[ P(1) \text{ é verdadeira} \]
e, para todo o \(n\geq 1\),
\[ P(1)\land P(2)\land \dots \land P(n) \Rightarrow P(n+1), \]
então:
\[ P(n) \text{ é verdadeira para todo o } n\geq 1. \]
A indução forte não é logicamente mais poderosa do que a indução ordinária: as duas formas são equivalentes. Contudo, em muitas demonstrações, a indução forte é mais natural e mais simples de aplicar.
Exemplo 1: fatorização em números primos
Um exemplo clássico de aplicação da indução forte é a demonstração de que todo o número natural maior do que \(1\) é primo ou pode ser escrito como produto de números primos.
Seja \(n>1\). Se \(n\) é primo, não há nada a demonstrar.
Se \(n\) não é primo, então existem dois inteiros \(a\) e \(b\), ambos maiores do que \(1\) e menores do que \(n\), tais que:
\[ n=ab. \]
Como \(a<n\) e \(b<n\), a hipótese da indução forte permite supor que \(a\) e \(b\) são primos ou produtos de números primos.
Por conseguinte, também \(n=ab\) é produto de números primos.
Este exemplo mostra por que razão, em certos contextos, é útil poder usar não apenas o caso imediatamente anterior, mas todos os casos precedentes.
Exemplo 2: a sucessão de Fibonacci
A sucessão de Fibonacci é definida por:
\[ F_1=1,\quad F_2=1,\quad F_n=F_{n-1}+F_{n-2} \quad \text{para todo o } n\geq 3. \]
Demonstremos por indução forte que, para todo o \(n\geq 1\),
\[ F_n<2^n. \]
Casos base
Para \(n=1\):
\[ F_1=1<2=2^1. \]
Para \(n=2\):
\[ F_2=1<4=2^2. \]
São necessários dois casos base porque a relação de recorrência define cada termo usando os dois termos anteriores.
Passo indutivo
Seja \(n\geq 3\). Suponhamos, por hipótese de indução forte, que a desigualdade é válida para todos os índices menores do que \(n\). Em particular:
\[ F_{n-1}<2^{n-1} \qquad \text{e} \qquad F_{n-2}<2^{n-2}. \]
Então:
\[ F_n=F_{n-1}+F_{n-2} < 2^{n-1}+2^{n-2}. \]
Como:
\[ 2^{n-1}+2^{n-2} = 2^{n-2}(2+1) = 3\cdot 2^{n-2}, \]
e como \(3<4\), obtemos:
\[ 3\cdot 2^{n-2} < 4\cdot 2^{n-2} = 2^2\cdot 2^{n-2} = 2^n. \]
Portanto:
\[ F_n<2^n. \]
Pelo princípio de indução forte, \(F_n<2^n\) para todo o \(n\geq 1\).
Este exemplo ilustra bem por que razão a indução forte é natural: a relação de recorrência \(F_n=F_{n-1}+F_{n-2}\) envolve os dois termos anteriores, não apenas o imediatamente precedente. Usar directamente a indução forte torna, por isso, o raciocínio mais linear.
Erros comuns nas demonstrações por indução
1. Esquecer o caso base
Sem o caso base, o passo indutivo não é suficiente. Demonstrar apenas:
\[ P(n)\Rightarrow P(n+1) \]
não garante que a propriedade seja verdadeira para algum número natural.
É como afirmar que cada peça derruba a seguinte, sem, no entanto, fazer cair a primeira peça.
2. Usar mal a hipótese de indução
A hipótese de indução deve ser usada exactamente na forma em que foi assumida.
Se se pretende demonstrar uma propriedade \(P(n+1)\), é necessário partir de \(P(n)\) e transformá-la correctamente no caso seguinte.
3. Demonstrar uma implicação incompleta
O passo indutivo deve ser válido para todo o valor de \(n\) pertencente ao domínio considerado.
Se o raciocínio funciona apenas para alguns valores de \(n\), a demonstração não é válida.
O paradoxo dos cavalos
Um exemplo célebre de falsa demonstração por indução é o chamado paradoxo dos cavalos.
Pretende-se demonstrar a seguinte afirmação:
\[ P(n): \quad \text{em qualquer conjunto de } n \text{ cavalos, todos os cavalos têm a mesma cor.} \]
Para \(n=1\), a propriedade é verdadeira: num conjunto formado por um único cavalo, todos os cavalos têm certamente a mesma cor.
Consideremos agora um conjunto de \(n+1\) cavalos:
\[ \{c_1,c_2,\dots,c_n,c_{n+1}\}. \]
Os primeiros \(n\) cavalos:
\[ \{c_1,c_2,\dots,c_n\} \]
têm todos a mesma cor, pela hipótese de indução. Também os últimos \(n\) cavalos:
\[ \{c_2,c_3,\dots,c_{n+1}\} \]
têm todos a mesma cor, igualmente pela hipótese de indução.
Como os dois subconjuntos se sobrepõem, pareceria seguir-se que todos os \(n+1\) cavalos têm a mesma cor.
O erro está na passagem de \(n=1\) para \(n=2\). Nesse caso os dois subconjuntos são:
\[ \{c_1\} \qquad \text{e} \qquad \{c_2\}, \]
e não têm nenhum elemento em comum. Não existe, portanto, nenhum cavalo partilhado que permita ligar a cor do primeiro à cor do segundo.
O passo indutivo não é válido para todos os valores de \(n\), mas apenas para \(n\geq 2\). A cadeia indutiva quebra-se precisamente na passagem de \(P(1)\) para \(P(2)\).
4. Confundir verificação numérica e demonstração
Verificar uma fórmula para \(n=1\), \(n=2\), \(n=3\) e \(n=4\) pode sugerir que ela é verdadeira, mas não constitui uma demonstração.
A indução não consiste em verificar muitos casos iniciais, mas em demonstrar um mecanismo geral de passagem do caso \(n\) para o caso \(n+1\).
Indução e definições recursivas
O princípio de indução está intimamente ligado às definições recursivas.
Muitos objectos matemáticos são definidos especificando:
- um ou mais valores iniciais;
- uma regra que permite construir os termos seguintes.
Por exemplo, o factorial é definido por:
\[ 0!=1 \]
e
\[ (n+1)!=(n+1)n!. \]
A recursão constrói os objectos passo a passo, enquanto a indução permite demonstrar propriedades válidas para todos os objectos construídos dessa forma.
Recursão e indução são, portanto, dois aspectos complementares da estrutura dos números naturais: a recursão define, a indução demonstra.
Conclusão
O princípio de indução matemática é muito mais do que uma técnica para demonstrar fórmulas. Exprime uma propriedade fundamental dos números naturais: cada número natural é atingido partindo do primeiro e aplicando repetidamente a operação de sucessor.
A sua força consiste em transformar uma afirmação infinita em duas verificações finitas:
- uma verificação inicial;
- uma regra de propagação do caso \(n\) para o caso \(n+1\).
Além disso, a equivalência com o princípio da boa ordem mostra que a indução está profundamente ligada à estrutura ordenada de \(\mathbb{N}\).
Por este motivo, o princípio de indução ocupa um papel central em álgebra, teoria dos números, lógica, análise discreta, informática teórica e em muitos outros domínios da matemática.
Em última análise, a indução matemática mostra como é possível governar o infinito através de um raciocínio finito, desde que a estrutura lógica seja construída com precisão.