Os números naturais. O método de indução matemática.
Material de estudo:
Começemos por introduzir um subconjunto especial de \(\mathbb{R}\): o conjunto dos números naturais, \(\mathbb{N}\). Se vos perguntarem o que são os números naturais vocês vão dizer que são os números \(1,\;2=1+1,\; 3=2+1,\; 4=3+1,\; 5=4+1,\;\dots\quad\) Como o conjunto dos naturais é infinito, por mais naturais que escrevamos nunca vai ser possível enumerá-los todos. Por isso, recorremos aos pontinhos "\(\dots\)". Do ponto de vista intuitivo é claro o que é que os pontinhos querem dizer, mas matematicamente não tem significado, a menos que escrevamos uma expressão (ou uma proposição) que, de uma forma precisa sem ambiguidades, nos caracterize todos os elementos de \(\mathbb{N}\), não só apenas um subconjunto finito, como fizemos atrás (em rigor, só dissemos que os números \(1,2,3,4,5\) são naturais).
Para definirmos o conjunto dos números naturais \(\mathbb{N}\) começemos por introduzir o seguinte conceito:
Definição: Um conjunto \(A\subset \mathbb{R}\) diz-se indutivo se,A segunda propriedade é conhecida também como propriedade hereditária.
- \(1\in A\),
- \(x\in A\;\Rightarrow\; x+1\in A.\)
Exemplos de conjuntos indutivos são: \[\mathbb{R},\quad \mathbb{R}^+,\quad \{1\}\cup \left[2,+\infty\right[,\quad \{1,2\}\cup \left[3,+\infty\right[,\quad \{1,2,3\}\cup \left[4,+\infty\right[.\]
Exemplos de conjuntos não indutivos são, qualquer conjunto com um número finito de elementos, \(\mathbb{R}^-\), o conjunto dos inteiros pares e o dos inteiros ímpares, qualquer intervalo \(\left[a,b\right]\) com \(b\) finito.
Vejamos agora, por exemplo, o número \(3\). Se \(A\) é um conjunto indutivo, então \(3\in A\), porque \(1\in A\;\Rightarrow\; 2=1+1\in A\;\Rightarrow\; 3=2+1\in A.\) Este raciocínio é válido para \(2,\;4,\;5,\;6\quad\) ou qualquer outro número que queremos incorporar no conjunto dos números naturais. Ou seja, vamos querer que \(\mathbb{N}\) esteja contido em todos os conjuntos indutivos. Por outro lado, não queremos, em \(\mathbb{N}\), mais números do que os que são obtidos desta forma. Isto motiva a seguinte
Definição: Define-se o conjunto dos números naturais como, \[\mathbb{N}= \text{intersecção de todos os conjuntos indutivos.}\]Reparem então que se \(A\) é indutivo, então \(\mathbb{N}\subset A\), fazendo de \(\mathbb{N}\) o menor conjunto indutivo possível. Como \(1>0\), então \(p\in\mathbb{N}\;\Rightarrow\; p>0\), ou seja, \[\mathbb{N}\subset\mathbb{R}^+\subset\mathbb{R}.\]
Este método resulta da definição de \(\mathbb{N}\) dada atrás. Seja \(A\) um conjunto de naturais (\(A\subset \mathbb{N}\)). Suponhamos que provamos que este conjunto é indutivo. Então, pela definição atrás, \(\mathbb{N}\subset A\). Concluimos então que \(A=\mathbb{N}.\) Seja agora, \(P(n)\) uma proposição, para cada valor da variável natural \(n\) (uma fórmula, uma desigualdade, etc.) Queremos certificamo-nos de que o conjunto \(A\) dos naturais \(n\) que fazem com que esta proposição é verdadeira é mesmo todo o \(\mathbb{N}\). Então, para isso, basta provar que \(A\) é indutivo, ou seja, \(P(1)\) é verdadeira (ou seja, \(1\in A\)) e \(P(n)\;\Rightarrow \;P(n+1)\) (ou seja, \(n\in A\;\Rightarrow\; n+1\in A\)).
Podemos enunciar então:
Teorema (método de indução matemática): Seja \(P(n)\) uma proposição, para cada \(n\in\mathbb{N}\). Se,então \(P(n)\) é verdadeira, para qualquer \(n\in\mathbb{N}\).
- \(P(1)\) é verdadeira,
- \(P(n)\Rightarrow P(n+1),\) para cada \(n\in\mathbb{N}\),
A afirmação "\(P(1)\) é verdadeira" designa-se por base de indução.
Para provar a segunda parte, assumimos que, para um valor de \(n\), \(P(n)\) é verdadeira - Hipótese de indução. Provamos, em seguida, que essa hipótese implica que \(P(n+1)\) é também verdadeira - Tese de indução.
Exemplo 1: Já conhecem o conceito de sucessão do Ensino Secundário. Seja \(x_n\) uma sucessão dada por recorrência da seguinte forma: \[\begin{cases} x_1=20,\\ x_{n+1}=2x_n,\quad n\in \mathbb{N}. \end{cases}\]
Depois de experimentarmos alguns valores, \(n=2,3,4,\dots\), conjecturamos que é verdadeira a expressão \(x_n=10\cdot 2^n,\) para todo \(n\in\mathbb{N}\). Queremos provar que assim é. A afirmação \(P(n)\) é "\(x_n=10\cdot 2^n\)". Então:\(P(n)\Rightarrow P(n+1)\):
Hipótese de indução \(\quad P(n)\): \(\quad x_n=10\cdot 2^n\).
Tese de indução \(\quad P(n+1)\): \(\quad x_{n+1}=10\cdot 2^{n+1}\).
Suponhamos então que a hipótese de indução é verdadeira para certo \(n.\) Então, \[x_{n+1}=2x_n=2(10\cdot 2^n)=10\cdot 2\cdot 2^n=10\cdot 2^{n+1}.\] Logo, a tese resulta verdadeira.
\(P(n)\Rightarrow P(n+1)\):
Hipótese de indução \(\quad P(n)\): \(\quad y_n=\dfrac{2\cdot (-1)^{n-1}}{(n-1)!}\).
Tese de indução \(\quad P(n+1)\): \(\quad y_{n+1}=\dfrac{2\cdot (-1)^{n}}{n!}\).
Suponhamos então que a hipótese de indução é verdadeira para certo \(n.\) Então, \[y_{n+1}=-\dfrac{y_n}{n}=-\dfrac{\dfrac{2\cdot (-1)^{n-1}}{(n-1)!}}{n}=-\dfrac{2\cdot (-1)^{n-1}}{(n-1)!n}=\dfrac{2\cdot (-1)^{n}}{n!}.\] Logo, a tese resulta verdadeira.
\(P(n)\Rightarrow P(n+1)\):
Hipótese de indução \(\quad P(n)\): \(\quad 1+3+5+\dots+(2n-1)=n^2\).
Tese de indução \(\quad P(n+1)\): \(\quad 1+3+5+\dots+(2(n+1)-1)=(n+1)^2\).
Observe que a soma correspondente à tese obtem-se da soma correspondente à hipótese somando a esta o termo \((2(n+1)-1)\). Por exemplo, \(P(3)\) é a igualdade \(\quad 1+3+5=3^2,\;\) enquanto que \(P(4)\) é a igualdade \(\; 1+3+5+7=4^2.\)
Suponhamos então que a hipótese de indução é verdadeira para certo \(n.\) Então, \[1+3+5+\dots+(2n-1)=n^2\] Somemos o termo \(2(n+1)-1\) a ambos os membros desta igualdade: \[1+3+5+\dots+(2n-1)+(2(n+1)-1)=n^2+(2(n+1)-1)=n^2+2n+1=(n+1)^2.\] Logo, a tese resulta verdadeira.
Definição: Seja \(a_n\) uma sucessão. Então, define-se por recorrência o somatório: \[\sum_{k=1}^1 a_k=a_1\,,\qquad \sum_{k=1}^{n+1}a_k=\sum_{k=1}^{n}a_k+a_{n+1}.\]
A expressão a provar no Exemplo 3 ficaria: \[\sum_{k=1}^n(2k-1)=n^2.\] Como Exercício faça a resolução deste Exemplo com esta notação.
Exemplo 4: Provar \[1+2+3+\dots+n=\sum_{k=1}^n k=\frac{n(n+1)}{2}.\]
Seja esta propriedade a proposição \(P(n)\). Provemos que é válida para todo \(n\in\mathbb{N}\).
\(P(n)\Rightarrow P(n+1)\):
Hipótese de indução \(\quad P(n)\): \(\quad \displaystyle\sum_{k=1}^n k=\frac{n(n+1)}{2}\).
Tese de indução \(\quad P(n+1)\): \(\quad \displaystyle \sum_{k=1}^{n+1} k=\frac{(n+1)(n+2)}{2}\).
Suponhamos então que a hipótese de indução é verdadeira para certo \(n.\) Então, de acordo com a definição de somatório dada atrás e a hipótese, \[\sum_{k=1}^{n+1} k=\sum_{k=1}^{n} k+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}.\] Logo, a tese resulta verdadeira.
\(P(n)\Rightarrow P(n+1)\):
Hipótese de indução \(\quad P(n)\): \(\quad \displaystyle\sum_{k=0}^n r^k=\frac{1-r^{n+1}}{1-r}\).
Tese de indução \(\quad P(n+1)\): \(\quad \displaystyle \sum_{k=0}^{n+1} r^k=\frac{1-r^{n+2}}{1-r}\).
Suponhamos então que a hipótese de indução é verdadeira para certo \(n.\) Então, de acordo com a definição de somatório dada atrás e a hipótese, \[\sum_{k=0}^{n+1} r^k=\sum_{k=0}^{n} r^k+r^{n+1}=\frac{1-r^{n+1}}{1-r}+r^{n+1}=\frac{1-r^{n+1}+r^{n+1}(1-r)}{1-r}=\frac{1-r^{n+2}}{1-r}.\] Logo, a tese resulta verdadeira.
\(P(n)\Rightarrow P(n+1)\):
Hipótese de indução \(\quad P(n)\): \(\quad 2^n\geqslant n+1\).
Tese de indução \(\quad P(n+1)\): \(\quad 2^{n+1}\geqslant n+2\).
Suponhamos então que a hipótese de indução é verdadeira para certo \(n.\) Então, \[2^n\geqslant n+1 \;\Rightarrow\; 2^{n+1}\geqslant 2(n+1)=2n+2.\] Observem que o último membro não corresponde ao segundo membro da expressão da tese onde queremos chegar. No entanto, podemos usar a propriedade transitiva, para obtermos a tese. Para isso comparamos os segundos membros da tese e da expressão anterior e vemos que precisamos da desigualdade \[2n+2\geqslant n+2.\] Mas, pela lei do corte, esta expressão é equivalente a \(n\geqslant 0\) que é obviamente verdadeira. Então, \[2^{n+1}\geqslant 2n+2\;\,\wedge\;\, 2n+2\geqslant n+2\quad\Rightarrow\quad 2^{n+1}\geqslant n+2,\] e a tese resulta verdadeira.
Este último exemplo é um caso particular da seguinte importante desigualdade conhecida como desigualdade de Bernoulli, para \(a>0\) fixo: \[(1+a)^n\geqslant 1+na,\] para qualquer \(n\in\mathbb{N}.\) Exercício: mostre o caso \(a=2\), ou seja, \(3^n\geqslant 2n+1.\)
Exemplo 7: Outra desigualdade: \[n!\geqslant 2^n, \quad\text{para } n\geqslant 4.\] .
\(P(n)\Rightarrow P(n+1)\) para \(n\geqslant 4\):
Hipótese de indução \(\quad P(n)\): \(\quad n!\geqslant 2^n\).
Tese de indução \(\quad P(n+1)\): \(\quad (n+1)!\geqslant 2^{n+1}\).
Suponhamos então que a hipótese de indução é verdadeira para certo \(n\geqslant 4.\) Então, \[n!\geqslant 2^n \;\Rightarrow\; n!(n+1)\geqslant 2^n(n+1)\;\Rightarrow\; (n+1)!\geqslant 2^n(n+1).\] Observem que novamente o último membro não corresponde ao segundo membro da expressão da tese onde queremos chegar. Tentemos usar novamente a propriedade transitiva. Provemos para isso que é verdadeira a desigualdade \[2^n(n+1)\geqslant 2^{n+1}.\] Mas esta resulta rapidamente da lei do corte: aquela expressão é equivalente a \(n+1\geqslant 2\) o que é universal. Concluimos então pela propriedade transitva que \[(n+1)!\geqslant 2^n(n+1)\;\wedge\;2^n(n+1)\geqslant 2^{n+1} \;\Rightarrow\; (n+1)!\geqslant 2^{n+1}\] Logo, a tese resulta verdadeira.
\(P(n)\Rightarrow P(n+1)\):
Hipótese de indução \(\quad P(n)\): \(\quad 4^n-1\) é múltiplo de \(3\).
Tese de indução \(\quad P(n+1)\): \(\quad 4^{n+1}-1\) é múltiplo de \(3\).
Suponhamos então que a hipótese de indução é verdadeira para certo \(n\geqslant 1.\) Então, \[4^{n+1}-1=(1+3)4^n-1=(4^n-1) +3\cdot 4^n\] é múltiplo de \(3\). Logo, a tese resulta verdadeira.