Ir ao conteúdo principal

Seção 2.1 Princípio de Indução

Suponhamos que queremos demonstrar que

\begin{equation*} 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} \end{equation*}

para qualquer número natural \(n\text{.}\) Esta fórmula se pode verificar facilmente para números pequenos tais como \(n = 1\text{,}\) 2, 3, ou 4, mas é impossível de verificar para todos os números naturais um por um. Para demonstrar que a fórmula é verdadeira em geral, é necessário um método mais genérico.

Suponhamos que temos verificado a equação para os primeiros \(n\) casos. Intentaremos demonstrar que podemos gerar uma fórmula para o caso \((n + 1)\) a partir deste conhecimento. A fórmula é verdadeira para \(n = 1\) pois

\begin{equation*} 1 = \frac{1(1 + 1)}{2}. \end{equation*}

Se temos verificado os primeiros \(n\) casos, então

\begin{align*} 1 + 2 + \cdots + n + (n + 1) & = \frac{n(n + 1)}{2} + n + 1\\ & = \frac{n^2 + 3n + 2}{2}\\ & = \frac{(n + 1)[(n + 1) + 1]}{2}. \end{align*}

Isso corresponde exatamente à fórmula para o caso \((n + 1)\text{.}\)

Este método de demonstração se conhece como indução matemática ou simplesmente indução se não há risco de confusão. Em vez de tentar verificar uma proposição sobre um subconjunto \(S\) dos inteiros positivos \({\mathbb N}\) um por um, uma tarefa impossível se \(S\) é um conjunto infinito, entregamos uma demonstração direita para o primeiro inteiro considerado, seguida de um argumento genérico mostrando que se a proposição se cumpre num certo caso, então também se cumpre para o seguinte caso na sucessão. Resumimos a indução matemática no seguinte axioma.

Para todos os inteiros \(n \geq 3\text{,}\) \(2^n \gt n + 4\text{.}\) Como

\begin{equation*} 8 = 2^3 \gt 3 + 4 = 7, \end{equation*}

a afirmação é verdadeira para \(n_0 = 3\text{.}\) Suponhamos que \(2^k \gt k + 4\) para \(k \geq 3\text{.}\) Então \(2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)\text{.}\) Mas

\begin{equation*} 2(k + 4) = 2k + 8 \gt k + 5 = (k + 1) + 4 \end{equation*}

pois \(k\) é positivo. Logo, por indução, a afirmação se cumpre para todos os inteiros \(n \geq 3\text{.}\)

O inteiro \(10^{n + 1} + 3 \cdot 10^n + 5\) é divisível por 9 para todo \(n \in {\mathbb N}\text{.}\) Para \(n = 1\text{,}\)

\begin{equation*} 10^{1 + 1} + 3 \cdot 10 + 5 = 135 = 9 \cdot 15 \end{equation*}

é divisível por 9. Suponhamos que \(10^{k + 1} + 3 \cdot 10^k + 5\) é divisível por 9 para \(k \geq 1\text{.}\) Então

\begin{align*} 10^{(k + 1) + 1} + 3 \cdot 10^{k + 1} + 5& = 10^{k + 2} + 3 \cdot 10^{k + 1} + 50 - 45\\ & = 10 (10^{k + 1} + 3 \cdot 10^{k} + 5) - 45 \end{align*}

é divisível por 9.

Demonstraremos o teorema do binômio por indução; ou seja,

\begin{equation*} (a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}, \end{equation*}

onde \(a\) e \(b\) são números reais, \(n \in \mathbb{N}\text{,}\) e

\begin{equation*} \binom{n}{k} = \frac{n!}{k! (n - k)!} \end{equation*}

é o coeficiente binomial. Primeiro mostraremos que

\begin{equation*} \binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}. \end{equation*}

Este resultado é a consequência de

\begin{align*} \binom{n}{k} + \binom{n}{k - 1} & = \frac{n!}{k!(n - k)!} +\frac{n!}{(k-1)!(n - k + 1)!}\\ & = \frac{(n + 1)!}{k!(n + 1 - k)!}\\ & =\binom{n + 1}{k}. \end{align*}

Se \(n = 1\text{,}\) o teorema do binômio é fácil de verificar. Agora suponhamos que o resultado é verdadeiro para \(n\) maior ou igual a 1. Então

\begin{align*} (a + b)^{n + 1} & = (a + b)(a + b)^n\\ & = (a + b) \left( \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}\right)\\ & = \sum_{k = 0}^{n} \binom{n}{k} a^{k + 1} b^{n - k} + \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n + 1 - k}\\ & = a^{n + 1} + \sum_{k = 1}^{n} \binom{n}{k - 1} a^{k} b^{n + 1 - k} + \sum_{k = 1}^{n} \binom{n}{k} a^k b^{n + 1 - k} + b^{n + 1}\\ & = a^{n + 1} + \sum_{k = 1}^{n} \left[ \binom{n}{k - 1} + \binom{n}{k} \right]a^k b^{n + 1 - k} + b^{n + 1}\\ & = \sum_{k = 0}^{n + 1} \binom{n + 1}{k} a^k b^{n + 1- k}. \end{align*}

Temos uma proposição equivalente ao Primeiro Princípio de Indução que as vezes será necessária.

Um subconjunto \(S\) de \({\mathbb Z}\) está bem-ordenado se todo subconjunto não vazio de \(S\) contém um menor elemento. Note que o conjunto \({\mathbb Z}\) não está bem-ordenado pois não contém um elemento mínimo. Os números naturais no entanto, sim estão bem-ordenados.

O Princípio da Bem-Ordem é equivalente ao Princípio de Indução.

Seja \(S = \{ n \in {\mathbb N} : n \geq 1 \}\text{.}\) Então \(1 \in S\text{.}\) Suponhamos que \(n \in S\text{.}\) Como \(0 \lt 1\text{,}\) temos \(n = n + 0 \lt n + 1\text{.}\) Portanto, \(1 \leq n \lt n + 1\text{.}\) Assim, se \(n \in S\text{,}\) então \(n + 1\) também deve estar em \(S\text{,}\) e pelo Princípio de Indução, \(S = \mathbb N\text{.}\)

Devemos mostrar que se \(S\) é um subconjunto não vazio dos números naturais, então \(S\) contém um elemento mínimo. Se \(S\) contém a 1, o teorema é verdadeiro pelo Lema 2.1.7. Suponhamos que se \(S\) contém um inteiro \(k\) tal que \(1 \leq k \leq n\text{,}\) então \(S\) contém um elemento mínimo. Mostraremos que se um conjunto \(S\) contém um inteiro menor ou igual a \(n + 1\text{,}\) então \(S\) tem um elemento mínimo. Se \(S\) não contém um elemento menor a \(n+1\text{,}\) então \(n+1\) é o menor inteiro em \(S\text{.}\) Do contrário, \(S\) deve conter um inteiro menor ou igual a \(n\text{.}\) Nesse caso, pela hipótese de indução, \(S\) contém um elemento mínimo.

A Indução pode ser muito útil na formulação de definições. Por exemplo, há duas formas de definir \(n!\text{,}\) o fatorial de um inteiro positivo \(n\text{.}\)

  • A definição explícita: \(n! = 1 \cdot 2 \cdot 3 \cdots (n - 1) \cdot n\text{.}\)

  • A definição indutiva ou recursiva: \(1! = 1\) e \(n! = n(n - 1)!\) para \(n \gt 1\text{.}\)

Olhar um problema de forma recursiva, em vez de explícita, frequentemente resulta numa melhor compreensão de situações complexas.