Teoria Conjunto dos números naturais

O princípio da indução finita é um conjunto de proposições utilizado para demonstrar que uma propriedade é válida para certo número $n_o$ natural e todos os seus sucessores.

As proposições (ou passos) do PIF são as seguintes:

1. Verificar que a propriedade vale para o número $n_o$ escolhido (geralmente $n_o = 0$ ou $n_o = 1$, mas há propriedades que começam do $2$, $3$ etc).

2. (Hipótese de indução) Assumir que a propriedade vale para algum $n \in \mathbb{N}$.

3. Demonstrar que a propriedade também vale para o sucessor $n+1$.

Se as três condições forem satisfeitas então a propriedade vale para qualquer $n \in \mathbb{N}$ tal que $n \geq n_o$.

O segredo para a indução finita é, no passo 3, fazer manipulações algébricas para encontrar a expressão do passo 2. Veja a seguir alguns exemplos de como isso funciona.

Vamos demonstrar que a soma dos $n$ primeiros números ímpares resulta em $n^2$:

$$1 + 3 + 5 + … + (2n- 1) = n^2$$

Obs.: Os números ímpares podem ser representados pelo termo geral $(2n- 1)$ com $n=1, 2, 3, …$

1. Vamos verificar que a soma do primeiro número ímpar resulta em $n^2$, isto é, que a propriedade é válida para $n_o = 1$.

$$n=1 \Rightarrow 1 = 1^2$$

2. Assumimos que a propriedade descrita vale para algum $n$, ou seja, é só reescrever a propriedade proposta:

$$1 + 3 + 5 + … + (2n- 1) = n^2$$

3. Vamos demonstrar que a propriedade continua valendo se somarmos o próximo número ímpar.

Obs.: Se último número ímpar vale $(2n- 1)$ o próximo ímpar será $2$ unidades maior, ou seja, $(2n + 1)$.

$$1 + 3 + 5 + … + (2n- 1) + (2n + 1)$$

Agora repare que os primeiros termos poder ser igualados a $n^2$, pois foi o que assumimos no item $2$:

$$\underbrace{1 + 3 + 5 + … + (2n- 1)} + (2n + 1) = \\
\hspace{-1.5em}= n^2 + 2n + 1$$

Agora, esta expressão pode ser fatorada como um trinômio quadrado perfeito:

$$n^2 + 2n + 1 = (n + 1)^2$$

Ou seja, a soma dos $(n+1)$ primeiros números ímpares resulta em $(n+1)^2$, como queríamos demonstrar.

Iremos demonstrar que a soma das $n$ primeiras potências de $2$, começando de $2^0$, resulta em $2^n- 1$. Em termos matemáticos:

$$2^0 + 2^1 + 2^2 + … + 2^{n-1} = 2^n- 1, \quad \forall n \in \mathbb{N^*}$$

1. Iremos verificar que a propriedade é válida para $n_o = 1$.

$$2^{1- 1} = 2^1- 1 \\
2^0 = 2- 1 \\
1 = 1 \color{green}{\checkmark}$$

2. Assumimos que é válida para algum $n\in \mathbb{N^*}$:

$$2^0 + 2^1 + 2^2 + … + 2^{n-1} = 2^n- 1$$

3. Iremos demonstrar que é válida para $n+1$:

$$2^0 + 2^1 + 2^2 + … + 2^{n-1} + 2^{n+1- 1} = \\
= \underbrace{2^0 + 2^1 + 2^2 + … + 2^{n-1}} + 2^{n} = \\
\hspace{2.9em} = 2^n- 1 + 2^n = \\
\hspace{2.9em} = 2^n + 2^n- 1 = \\
$$

Repare que podemos somar $2^n + 2^n = 2 \cdot 2^n$, pois são a mesma “coisa”; se não acredita em mim, substitua $2^n = x$:

$$2^n + 2^n = x + x = 2x$$

Mas $x$ não vale $2^n$?

$$2^n + 2^n = x + x = 2x = 2 \cdot 2^n$$

Vamos retornar aonde paramos:

$$2^n + 2^n- 1 = \\
=2 \cdot 2^n- 1 = \\
= 2^{n+1}- 1$$

Isso significa que a soma dos $n+1$ primeiras potências de $2$ resulta em $2^{n+1}- 1$, como queríamos demonstrar.

O número $n \cdot (n+1) \cdot (n+2)$ é divisível por $6$ para qualquer $n \in \mathbb{N}$.

1. Iremos verificar que a propriedade é válida para $n_o = 0$.

$$0 \cdot (0 +1) \cdot (0 + 2) = 0 \cdot 1 \cdot 2 = 0$$

E $0$ é divisível por $6$.

2. Vamos assumir que o número $n \cdot (n+1) \cdot (n+2)$ é divisível por $6$.

3. Vamos demonstrar que a propriedade é válida para $n+1$.

$$(n+1)(n+1 + 1)(n +1 +2) = \\
= (n + 1)(n + 2)(n + 3)$$

A estratégia, nesse 3º passo, sempre é a de encontrar a expressão do item 2. Então vamos distribuir as multiplicações e ver se a encontramos:

$$ (n + 1)(n + 2)(n + 3) = \\
= (n^2 + 2n + n + 2)(n+3) = \\
= (n^2 + 3n + 2)(n +3) = \\
= n^3 + 3n^2 + 3n^2 + 9n + 2n + 6 = \\
= n^3 + 6n^2 + 11n + 6$$

Mas o que esta expressão tem a ver com a do item 2? Vamos voltar e distribui-la também para descobrir:

$$n \cdot (n+1) \cdot (n+2) = \\
= n(n^2 + 2n + n + 2) = \\
= n (n^2 + 3n + 2) = \\
= n^3 + 3n^2 + 2n$$

Ou seja, podemos separar a expressão do item 3 da seguinte forma:

$$n^3 + 6n^2 + 11n + 6 = (n^3 + 3n^2 + 2n) + (3n^2 + 9n + 6) = \\
(n^3 + 3n^2 + 2n) + 3 (n^2 + 3n + 2)$$

Vamos fatorar de volta a parte $3 (n^2 + 3n + 2)$:

$$(n^3 + 3n^2 + 2n) + 3(n+1)(n+2)$$

A parte $(n^3 + 3n^2 + 2n)$ é divisível por $6$ pois é consequência direta do item 2. E vemos que a parte $3(n+1)(n+2)$ também é, pois já é múltipla de $3$ e se $(n+1)$ não for um número par, então $(n+2)$ é par.

Então demonstramos que a propriedade também é válida para $n+1$, e portanto, a hipótese inicial é válida.

Vamos demonstrar que todo número da forma $3^{2n+1} + 2^{n-1}$, com $n \in \mathbb{N^*}$, é divisível por $7$.

1. Vamos verificar que funciona para $n_o = 1$.

$$3^{2 \cdot 1 +1} + 2^{1-1} = \\
= 3^3 + 2^0 = \\
= 27 + 1 = 28$$

Como $28$ é divisível por $7$, está verificado.

2. Vamos assumir que a propriedade vale para algum $n \in \mathbb{N^*}$.

$$3^{2n+1} + 2^{n-1} \text{ é divisível por }7$$

3. Vamos demonstrar que para $n+1$ a propriedade continua válida.

$$3^{2(n+1) + 1} + 2^{(n+1)- 1} = \\
= 3^{2n +3} + 2^{n}$$

O objetivo agora é fazer a expressão $3^{2n+1} + 2^{n-1}$ aparecer; então vamos utilizar as propriedades de potência:

$$3^{2n + 3} + 2^{n} = \\
= 3^{2n + 1 \color{red}{+ 2}} + 2^{n-1 \color{blue}{+ 1}} = \\
= \color{red}{3^2} \cdot 3^{2n+1} + \color{blue}2 \cdot 2^{n- 1} \\
= 9 \cdot 3^{2n+1} + 2 \cdot 2^{n- 1} = \\
= 7 \cdot 3^{2n+1} + 2 \cdot 3^{2n+1} 2 \cdot 2^{n- 1} \\
= 7 \cdot 3^{2n+1} + 2(3^{2n+1} +2^{n- 1})$$

Agora repare que a expressão $7 \cdot 3^{2n+1}$ é divisível por $7$; e, por hipótese de indução, $3^{2n+1} +2^{n- 1}$ também é divisível por $7$. Portanto o número todo é divisível por $7$.

Iremos provar que $n! > 2^n$ para qualquer $n \geq 4, n \in \mathbb{N}$.

1. Provamos que para $n_o = 4$ a desigualdade é verdadeira:

$$4! > 2^4 \\
4 \cdot 3 \cdot 2 \cdot 1 > 2 \cdot 2 \cdot 2 \cdot 2 \\
\hspace{0.6em}24 > 16 \color{green}{\checkmark}$$

2. Vamos assumir que a propriedade vale para algum $n \geq 4, n \in \mathbb{N}$.

$$n! > 2^n$$

3. Vamos demonstrar que funciona também para $n+1$

$$(n+1) ! > 2^{n+1} \\
(n+1) \cdot n! > 2 \cdot 2^n$$

Dividimos os dois lados da desigualdade por $n!$

$$\dfrac{(n+1) \cdot n ! }{n ! } > \dfrac{2 \cdot 2^n}{n!} \\
n+1 > 2 \cdot \dfrac{2^n}{n!}$$

E agora verificamos que é verdade, pois, como $n \geq 4$, temos que $n+1 \geq 5$; no segundo membro, graças à hipótese de indução, temos que:

$$n! > 2^n \Rightarrow 1 > \dfrac{2^n}{n!}$$

Então, no segundo membro, $2 \cdot \dfrac{2^n}{n!} < 2$.

Algumas pessoas podem achar que o passo 3 não fica tão elegante desta maneira. Caso queira uma maneira mais “limpa”, podemos começar com a desigualdade:

$$n! > 2^n$$

Multiplicar os dois lados por $(n+1)$

$$(n+1) n! > 2^n (n+1) \\
(n+1) !> 2^n (n+1)$$

Agora, começamos com outra desigualdade, que é válida para $n \geq 4$:

$$n +1 > 2$$

E multiplicamos os dois lados por $2^n$

$$2^n (n +1) > 2 \cdot 2^n \\
2^n (n + 1) > 2^{n + 1}$$

Então juntamos as duas desigualdades:

$$(n+1) !> 2^n (n+1) > 2^{n + 1}$$

E, por transitividade,

$$(n+1) !> 2^{n + 1}$$

Iremos provar que

$$(1+1) \cdot \left(1 + \dfrac{1}{2} \right) \cdot \left(1 + \dfrac{1}{3} \right) \dots \left(1 + \dfrac{1}{n} \right) = n +1$$

para qualquer $n \in \mathbb{N^*}$.

1. Vamos verificar que funciona para $n_o = 1$.

$$\left(1 + \dfrac{1}{1} \right) = 1 + 1 \\
2 = 2 \color{green}{\checkmark}$$

2. Vamos assumir que a propriedade é válida para algum $\in \mathbb{N^*}$

$$(1+1) \cdot \left(1 + \dfrac{1}{2} \right) \cdot \left(1 + \dfrac{1}{3} \right) \dots \left(1 + \dfrac{1}{n} \right) = n +1$$

3. Agora queremos demonstrar que é válida para $n+1$. Então vamos partir desta expressão e multiplicar pelo próximo termo:

$$(1+1) \cdot \left(1 + \dfrac{1}{2} \right) \cdot \left(1 + \dfrac{1}{3} \right) \dots \left(1 + \dfrac{1}{n} \right) \cdot \left(1 + \dfrac{1}{n+1} \right) $$

O $n$ primeiros termos podem ser trocados por $n+1$, pela hipótese de indução:

$$\underbrace{(1+1) \cdot \left(1 + \dfrac{1}{2} \right) \cdot \left(1 + \dfrac{1}{3} \right) \dots \left(1 + \dfrac{1}{n} \right)} \cdot \left(1 + \dfrac{1}{n+1} \right) = \\
\hspace{-2em}= (n+ 1) \cdot \left(1 + \dfrac{1}{n+1} \right) = \\
= n + 1 + \dfrac{n+1}{n+1} = \\
= n +1 + 1 = \\= n +2$$

Portanto,

$$(1+1) \cdot \left(1 + \dfrac{1}{2} \right) \cdot \left(1 + \dfrac{1}{3} \right) \dots \left(1 + \dfrac{1}{n} \right) \cdot \left(1 + \dfrac{1}{n+1} \right) = (n+1) + 1$$

CQD.

Iremos demonstrar que

$$1^3 + 2^3 + … + n^3 = \left [ \dfrac{n(n+1)}{2} \right] ^2$$

para qualquer $n \in \mathbb{N}$. Para facilitar, vamos utilizar uma expressão equivalente:

$$1^3 + 2^3 + … + n^3 = \dfrac{n^2(n+1)^2}{4}$$

1. Primeiro verificamos que a propriedade vale para $n_o = 0$

$$0^3 = \dfrac{0^2 (0+1)}{4} \\
0 = 0 \color{green}{\checkmark}$$

2. Assumimos que a propriedade vale para algum $n \in \mathbb{N}$.

$$1^3 + 2^3 + … + n^3 = \dfrac{n^2(n+1)^2}{4}$$

3. Vamos demonstrar que é válida para $n+1$. Iremos começar com a expressão do item 2 e somar $(n+1)^3$ dos dois lados, o que seria o próximo termo:

$$1^3 + 2^3 + … + n^3 + (n+1)^3 = \dfrac{n^2(n+1)^2}{4} + (n+1)^3$$

Vamos trabalhar apenas com o segundo membro; nele, tomamos $(n+1)^2$ como fator comum:

$$\dfrac{n^2(n+1)^2}{4} + (n+1)^3 = \\
= (n+1)^2 \cdot \left (\dfrac{n^2}{4} + n+1 \right)$$

Agora vamos somar o que está dentro do parênteses

$$ (n+1)^2 \cdot \left (\dfrac{n^2}{4} + n+1 \right) = \\
= (n+1)^2 \cdot \left (\dfrac{n^2+ 4n + 4}{4}\right) $$

E perceba que a segunda expressão é um trinômio quadrado perfeito; vamos fatorá-la:

$$ (n+1)^2 \cdot \left (\dfrac{n^2+ 4n + 4}{4}\right) = \\
= (n+1)^2 \dfrac{(n+2)^2}{4} = \\
= \dfrac{(n+1)^2 (n+2^2)}{4}$$

Ou seja, provamos que:

$$1^3 + 2^3 + … + n^3 + (n+1)^3 = \dfrac{(n+1)^2 (n+2^2)}{4}$$

que é a propriedade aplicada para $n+1$.