Texto-base - Indução Matemática | Adriano Thomaz

A Teoria dos Números preocupa-se com as propriedades dos inteiros e, particularmente sob os aspectos mais elementares, dos inteiros positivos $\{1\text{,}2\text{,}3\text{,}...\}$. Dessa forma, assume-se a partir desse ponto, a utilização dos axiomas definidos por Giuseppe Peano para os números naturais:

1. Zero é um número natural.
2. Todo número natural tem sucessor.
3. Zero é o único natural que não é sucessor de outro número.
4. Se dois números têm o mesmo sucessor, então eles são iguais.
5. Se um conjunto contém o zero e os sucessores de todos os seus elementos, então esse conjunto é o conjunto dos números naturais.

A partir desse último axioma, da indução, decorre um instrumento bastante importante nas demonstrações matemáticas, que é o Princípio da Indução. Antes, porém, faz-se necessário recordar um fato elementar relacionado com o conjunto dos inteiros, que é o Princípio do Menor Inteiro. Esse princípio desempenha um papel importante nas demonstrações desse curso. Ele também é conhecido como Princípio da Boa Ordem ou Boa-Ordenação, como disposto a seguir:

Princípio do Menor Inteiro. Todo conjunto não vazio $S$ de inteiros não negativos contém um menor elemento; ou seja, existe um inteiro $m$ em $S$ tal que $m\le n$ para todo $n$ que pertence a $S$.

$\forall S\subseteq {\mathbb{Z}}^{+}\text{,}S\ne \varnothing \text{,}\&exists;m\in S\text{:}m\le n\text{,}\forall n\in S$

O conjunto dos inteiros positivos tem o que é conhecido como propriedade Arquimediana, como segue:

Propriedade Arquimediana. Se $a$ e $b$ são inteiros positivos quaisquer, então existe um inteiro positivo $n$ tal que $na\ge b$.

Demonstração. Admita que o enunciado da propriedade Arquimediana não seja verdadeiro, logo para algum par $a$ e $b$, $na<b$ para todo inteiro positivo . Então o conjunto

$S=\{b-na\text{;}n\in {\mathbb{Z}}_{*}^{+}\}$

possui apenas inteiros positivos. Pelo Princípio do Menor Inteiro, $S$ possuirá um menor elemento, por exemplo, $b-ma$. Observe que $b-(m+1)a$ também está em $S$, pois $S$ contém todos os inteiros desta forma. Além disso, temos:

$b-(m+1)a=(b-ma)-a<b-ma$

o que contraria a escolha de  $b-ma$ como o menor inteiro de $S$. Esta contradição surgiu de nosso pressuposto de que a propriedade Arquimediana não é válida; por isso esta propriedade é verdadeira.

Utilizando o Princípio do Menor Inteiro pode-se deduzir o Princípio da Indução Finita, que fornece as bases para um método de demonstração chamado indução matemática. De forma simplificada, o Princípio da Indução Finita afirma que, se um conjunto de inteiros positivos tem duas propriedades específicas, então ele é o conjunto de todos os inteiros positivos.

Primeiro Princípio da Indução Finita. Seja $T$ um subconjunto de inteiros positivos com as seguintes propriedades:

1. O inteiro $1$ pertence a $T$.
2. Sempre que o inteiro $k$ está em $T$, o próximo inteiro $k+1$ também está em $T$.

Então $T$ é o conjunto de todos os inteiros positivos.

Demonstração. Seja $S$ o conjunto de todos os inteiros positivos que não pertencem a $T$, e admita que $S$ seja não vazio. O Princípio do Menor Inteiro nos diz que $S$ possui um menor elemento, que denotamos por $a$. Como $1$ está em $T$, certamente $a>1$, e então $0<a-1<a$. A escolha de $a$ como o menor inteiro positivo em $S$ implica que $a-1$ não é um elemento de $S$, ou o que é equivalente, que $a-1$  pertence a $T$. Por hipótese, $T$  deve também conter $(a-1)+1=a$, o que contradiz o fato de que $a$ encontra-se em $S$. Concluímos que o conjunto $S$ é vazio e consequentemente que $T$ contém todos os inteiros positivos. 

Pode-se utilizar a indução matemática para uma tentativa de provar enunciados sobre os inteiros positivos. Porém, vale destacar que, mesmo que a indução matemática seja capaz de fornecer uma técnica padrão para essas provas, ela não ajuda na formulação de enunciados. Contudo, se fazemos inferências sobre a propriedade que acreditamos que pode ser generalizada, então sua validade pode ser testada por indução matemática.

Observação. Quando se realiza provas por indução, geralmente encurta-se o argumento pela eliminação de todas as referências ao conjunto , e procedemos para mostrar que o resultado em questão é verdadeiro para o inteiro , e, se verdadeiro para o inteiro , é, então, também verdadeiro para.

Importante verificar ambas as condições do Princípio de Indução Finita antes de qualquer conclusão, pois nenhuma condição é suficiente sozinha. A demonstração da condição (a) é usualmente chamada de base para a indução, e a demonstração da (b) é chamada o passo de indução.

As suposições feitas na realização do passo de indução são conhecidas como hipóteses de indução. A prova por indução pode ser pensada como a brincadeira, comparamos a uma linha infinita de dominós, todos de pé e dispostos de tal forma que, quando um cai, derruba o próximo na linha. Se o dominó não é empurrado não há base para a indução, ou se o espaçamento é muito grande o passo de indução falha, então uma linha completa não cairá.

Existe uma variante do princípio da indução que é frequentemente usada quando só o Primeiro Princípio parece ineficaz. Como na primeira versão, o Segundo Princípio da Indução Finita oferece duas condições que asseguram que um determinado conjunto de inteiros positivos é composto por todos os inteiros positivos.

O que acontece é o seguinte: mantemos a exigência (a), mas (b) é substituída por (b′), então $k+1$ também deve estar em $S$.

Segundo Princípio da Indução Finita. Seja $T$ um subconjunto de inteiros positivos com as seguintes propriedades:

a) O inteiro $1$ pertence a $T$.

b) Se $k$ é um inteiro positivo tal que $1,2,...,k$ pertencem a $T$, então $k+1$ também deve estar em $T$.

Então $T$ é o conjunto de todos os inteiros positivos.

O Primeiro Princípio da Indução Finita é mais usado que o Segundo, porém há ocasiões em que o Segundo é mais adequado. Às vezes acontece de, na tentativa de mostrar que $k+1$ é um elemento de $T$, precisamos provar o fato de que não só $k$, mas todos os inteiros positivos que precedem $k$, estão em $T$.

Nossa formulação destes princípios de indução tem sido para o caso em que a indução começa com 1. Cada forma pode ser generalizada para começar com qualquer inteiro positivo $a$.

Segundo Princípio da Indução Finita (variação). Seja $a$ um número natural e $P(n)$ uma propriedade referente a todo natural maior ou igual que $a$ tal que:

a) A propriedade é válida para $a$, ou seja, $P(a)$ é verdadeira.

b) Se propriedade vale para $n$, então vale para $(n+1)$. Isso quer dizer, $P(n)\Rightarrow P(n+1)$.

Então, $P(n)$  é verdadeira para todo natural maior ou igual a $a$.

Nesta circunstância, a conclusão passa a ser “Então $T$ é o conjunto de todos os inteiros positivos $n\ge a$”.

A indução matemática é frequentemente usada tanto como um método de definição quanto como um método de demonstração.

Referências

Texto adaptado de BURTON, David M. Teoria elementar dos números. 7.ed. Rio de Janeiro: LTC, 2016.