Princípio da indução matemática

---

O Princípio da Indução Finita, abreviado como PIF-I, é uma poderosa ferramenta na matemática para provar proposições que envolvem conjuntos de números naturais.

Ele opera da seguinte maneira:

Suponhamos que temos uma proposição $p(n)$ que desejamos provar para todo número natural n pertencente ao conjunto M, onde $M$ é definido como $M=n\in N|n\ge m\text{ e }m\in N$. Para aplicar o PIF-I, precisamos atender a duas condições fundamentais:

I. Primeiramente, devemos demonstrar que a proposição $p(m)$ é verdadeira para um valor específico $m$ (isso é conhecido como a “base indutiva”).

II. Em seguida, precisamos mostrar que, assumindo que a proposição é verdadeira para algum número $k$ pertencente a $M$, podemos provar que ela também é verdadeira para o próximo número $k+1$ (isso é chamado de “passo indutivo”).

Se ambas as condições (I) e (II) forem atendidas, podemos concluir que a proposição $p(n)$ é verdadeira para todos os números naturais $n$ pertencentes ao conjunto $M$.

Em essência, o PIF-I nos fornece uma estratégia eficaz de prova chamada de prova por indução. Começamos estabelecendo a validade da proposição para um valor inicial (base indutiva) e, em seguida, demonstramos que, se a proposição é válida para algum número $k$, ela também deve ser válida para o próximo número $k+1$ (passo indutivo). Esse processo assegura que a proposição seja verdadeira para todos os números naturais dentro do conjunto $M$.

Essa técnica é especialmente útil quando lidamos com propriedades que seguem uma espécie de padrão ou sequência, como é frequentemente o caso em problemas matemáticos. Ela se relaciona com o conceito de “boa ordem” mencionado na resposta anterior, pois ajuda a estabelecer a validade de proposições para todos os elementos de um conjunto ordenado, como os números naturais.

Exercício 1

Prove por indução que $p(n):n<2n,\forall n\in \mathbb{N},n\ge 0$

Passo 1: Base da indução (n = 0)

Primeiro, verificamos se a afirmação $p(n)$ é verdadeira para $n=0$:

$$0<2\cdot 0$$

Claramente, $0<0$ não é verdadeiro. Portanto, a base da indução não é satisfeita para $n=0$.

Passo 2: Hipótese da indução

Suponha que a afirmação $p(k)$ seja verdadeira para um número natural $k$. Ou seja, supomos que:

$$k<2k$$

Passo 3: Passo da indução

Agora, precisamos mostrar que a afirmação $p(n)$ é verdadeira para $n=k+1$. Ou seja, precisamos mostrar que:

$$(k+1)<2(k+1)$$

Vamos simplificar a desigualdade do lado direito:

$$2(k+1)=2k+2$$

Agora, podemos comparar o lado esquerdo com o lado direito da desigualdade:

$$(k+1)<2k+2$$

Agora, subtraímos $k$ de ambos os lados:

$$1<k+2$$

Subtraindo 2 de ambos os lados:

$$-1<k$$

Como já sabemos que $k$ é um número natural ($k\in \mathbb{N}$), essa desigualdade é sempre verdadeira.

Portanto, para $n=k+1$, temos:

$$(k+1)<2(k+1)$$

Isso conclui o passo da indução.

Conclusão

Com base na base da indução (Passo 1) e no passo da indução (Passo 3), podemos concluir que a afirmação $p(n):n<2n$ é verdadeira para todos os números naturais $n$ onde $n\ge 0$, utilizando o princípio da indução finita.

Exercício 2

Prove por indução que $p(n):2n<n!,\forall n\in N,n>3$

Para provar por indução que $p(n):2^n<n!$, para todos $n\in \mathbb{N}$ onde $n>3$, vamos seguir os passos do princípio da indução finita.

Passo 1: Base da indução (n = 4)

Primeiro, verificamos se a afirmação $p(n)$ é verdadeira para $n=4$:

$$2^4<4!$$

Simplificando:

$$16<24$$

Claramente, $16<24$ é verdadeiro. Portanto, a base da indução é satisfeita para $n=4$.

Passo 2: Hipótese da indução

Suponha que a afirmação $p(k)$ seja verdadeira para um número natural $k$. Ou seja, supomos que:

$$2^k<k!$$

Passo 3: Passo da indução

Agora, precisamos mostrar que a afirmação $p(n)$ é verdadeira para $n=k+1$. Ou seja, precisamos mostrar que:

$$2^{k+1}<(k+1)!$$

Vamos começar com o lado esquerdo da desigualdade:

$$2^{k+1}=2\cdot 2^k$$

Agora, usando nossa hipótese de indução (Passo 2), sabemos que:

$$2^k<k!$$

Multiplicando ambos os lados por 2:

$$2\cdot 2^k<2\cdot k!$$

Simplificando:

$$2^{k+1}<2k!$$

Agora, vamos considerar o lado direito da desigualdade:

$$(k+1)!=(k+1)\cdot k!$$

Multiplicando ambos os lados por 2:

$$2(k+1)!=2(k+1)\cdot k!$$

Agora, podemos comparar o lado esquerdo com o lado direito da desigualdade:

$$2^{k+1}<2(k+1)!$$

Isso conclui o passo da indução.

Conclusão

Com base na base da indução (Passo 1) e no passo da indução (Passo 3), podemos concluir que a afirmação $p(n):2^n<n!$ é verdadeira para todos os números naturais $n$ onde $n>3$, utilizando o princípio da indução finita.

Referências

---

Matemática Discreta - Aula 18.pdf