Tomando \(X=\{ n\in \mathbb{N}~|~P(n_0+n-1) \text{ é válida} \}\text{.}\) Então, \(1\in X\text{,}\) já que, por i., \(P(n_0+1-1)=P(n_0)\) é válida. Além disso, por ii., se \(n\in X\text{,}\) então \(n+1\in X\text{.}\) Logo, pelo Axioma da Indução, \(X=\mathbb{N}\text{.}\)
Exemplo2.2.2.
Mostre que \(2^n>n^2\) para todo natural \(n\geq 5\text{.}\)
Se \(P(n)\) é a sentença \(2^n> n^2\text{,}\) temos \(P(5)\) verdadeira. Suponhamos, agora, que \(P(n)\) seja verdadeira, ou seja, \(2^n>n^2\text{,}\) para algum \(n\geq 5\text{.}\) Multiplicando ambos os membros por \(2\text{,}\) obtemos \(2^{n+1}>2n^2\text{.}\) Agora, precisamos mostrar que \(2n^2>(n+1)^2\text{.}\)
Daí, concluímos que \(2^{n+1}>(n+1)^2\text{,}\) ou seja, que \(P(n+1)\) é verdadeira. Logo, pelo Teorema 2.2.1, a desigualdade vale para todo \(n\geq 5\text{.}\)
Outra variante do Princípio da Indução ocorre quando convém, no passo de indução, considerar a validez não somente do antecessor direto, mas de 2 ou mais antecessores.
Exemplo2.2.4.
Considere a sequência em que \(a_1=1, a_2=2\) e \(a_{n+2}=2a_{n+1}-a_n\text{,}\) para todo natural \(n\text{.}\) Mostre que o termo geral é \(a_n=n\text{.}\)
Se tentarmos proceder como nos casos anteriores e considerarmos a sentença \(P(n): a_n=n,\) o mecanismo de indução não funciona. Não conseguimos passar de \(P(n)\) para \(P(n+1)\text{,}\) pois \(P(n+1)\) depende não somente de \(P(n)\text{,}\) mas também de \(P(n-1)\text{.}\) Para fazer a prova, considere uma sentença que estabeleça a validez da expressão do termo geral para dois valores consecutivos de \(n\text{.}\) Podemos tomar \(Q(n): P(n)\) e \(P(n+1)\text{,}\) ou seja, \(Q(n): a_n=n\) e \(a_{n+1}=n+1\text{.}\)
Agora, temos que \(Q(1)\) é verdadeira, já que ambas \(P(1): a_1=1\) e \(P(2): a_2=2\) são verdadeiras. Além disso, se supomos que \(Q(n)\) é verdadeira para algum \(n\text{,}\) temos que \(P(n): a_n=n\) e \(P(n+1): a_{n+1}=n+1\) são verdadeiras. Daí:
Assim \(P(n+2): a_{n+2}=n+2\) é verdadeira e, em consequência, \(Q(n+1): P(n+1)\) e \(P(n+2)\) também o é. Logo, pelo Princípio da Indução, \(Q(n)\) é válida para todo \(n\in \mathbb{N}\text{.}\) Em consequência, \(P(n): a_n=n\) é também válida para todo \(n\in \mathbb{N}\text{.}\)
Podemos generalizar o que fizemos acima enunciando a seguinte forma do Princípio da Indução:
Teorema2.2.5.
Seja \(P(n)\) uma sentença aberta relativa ao número natural \(n\text{.}\) Suponhamos que
\(P(1), P(2, \ldots, P(k))\) são verdadeiras.
Para todo \(n\geq n_0\text{,}\) a validez de \(P(n), P(n+1), \ldots, P(n+k-1)\) implicam a validez de \(P(n+k)\text{.}\)
Então \(P(n)\) é válida para todo \(n\in\mathbb{N}\text{.}\)
Uma outra variante do Princípio da Indução é muitas vezes chamada de Princípio da Indução Completa ou da Indução Forte. Nela, a hipótese de indução é a validez da propriedade para todos os naturais menores que ou iguais a um natural \(n\text{:}\)
Teorema2.2.6.
Seja \(P(n)\) uma propriedade relativa ao número natural \(n\text{.}\) Suponhamos que
\(P(1)\) é válida.
Para todo \(n\text{,}\) a validez de \(P(k)\text{,}\) para todo \(k\leq n\text{,}\) implica a validez de \(P(n+1)\text{.}\)
Então \(P(n)\) é válida para todo \(n\in \mathbb{N}\text{.}\)
Consideremos a sentença aberta \(Q(n): P(k)\) é válida, para todo natural \(k\leq n\text{.}\) Como, por i., \(P(1)\) é válida, \(Q(1)\) também é. Suponhamos agora que \(Q(n)\) seja válida. Isto quer dizer que \(P(k)\) é válida, para todo \(k\leq n\text{.}\) Mas, por ii., isto implica a validez de \(P(n+1)\text{,}\) que por sua vez implica que \(P(k)\) seja válida para todo \(k\leq n+1\text{.}\) Logo, \(Q(n+1)\) também é válida. Portanto, pela forma original do Princípio da Indução, \(Q(n)\) é válida para todo \(n\in \mathbb{N}\text{,}\) de onde decorre a validez de \(P(n)\) para todo \(n\in \mathbb{N}\text{.}\)
Naturalmente, o mecanismo da indução completa pode ser adaptado para demonstrar propriedades que valem a partir de um número natural \(n_0\text{.}\) Neste caso, a hipótese de indução é a validez de \(P(k)\) para todo natural \(k\) tal que \(n_0\leq k\leq n\text{.}\)
o que sugere que \(a_n=1\text{,}\) para todo \(n\geq 1\text{,}\) com \(a_0=2\text{.}\)
Mostrar que \(a_n\) está bem definido, e é dado pela expressão acima, requer o uso de Indução Completa, já que a definição de cada termo é baseada no valor de todos os antecessores. Como \(a_1=1\text{,}\)\(P(n): a_n=1\) é válida para \(n=1\text{.}\) Suponhamos, agora, que \(P(k)\) seja válida (isto é, \(a_k=1\)) para todo \(k\) tal que \(1\leq k\leq n\text{.}\) Usando este fato e o de que \(a_0=2\text{,}\) obtemos
o que mostra que \(P(n+1)\) é verdadeira. Logo, o Princípio da Indução Completa assegura que \(P(n): a_n=1\) é válida para todo \(n\geq 1\text{.}\)
Outra aplicação de indução completa é a prova da Propriedade da Boa Ordenação.
Teorema2.2.8.(O Princípio da Boa Ordenação).
Todo subconjunto não vazio \(X\subset \mathbb{N}\) possui um menor elemento. Isto significa que existe um elemento \(x_0\in X\) que é menor do que todos os demais elementos de \(X\text{.}\)
\(P(1)\) é válida. De fato, \(1\notin X\text{,}\) já que se \(1\) pertencesse a \(X\) seria seu menor elemento. Em consequência \(1\in X^c\text{.}\)
Suponha que \(P(k)\) seja válida, para todo \(k\leq n\text{.}\) Isto quer dizer que todos os naturais de \(1\) a \(n\) estão em \(X^c\text{,}\) ou seja, que não estão em \(X\text{.}\) Mas isto implica que \(n+1\) não pode pertencer a \(X\text{,}\) já que, neste caso, seria seu menor elemento e, por hipótese, \(X\) não possui menor elemento. Logo, \(n+1\in X^c\text{,}\) o que mostra que \(P(n+1)\) é válida.
Logo, pelo Princípio da Indução Completa, \(P(n)\) é válida para todo \(n\in \mathbb{N}\text{,}\) isto é, \(X^c=\mathbb{N}\) e \(X=\emptyset\text{.}\)
