Matemática, perguntado por Lukyo, 3 meses atrás

(Aritmética – Teoria dos Números – Números naturais – Princípio da Indução Finita)

Seja $A=\{n\in\mathbb{N}:~7\,|\,2^{3n-1}+3^{6n-5}\}.$

Utilizando o Princípio da Indução Finita, mostre que $A=\mathbb{N}.$

gabrielcguimaraes: Quanto à esse princípio, imagino que funciona demonstrando que, se existe n ∈ A, então existe n + 1 ∈ A, e se existe este último, então existe n + 2 ∈ A, e tudo mais. Mas se provei que existe n, por que o caso base?

Lukyo: A não pode ser vazio, tem que ter algum elemento. Porque a prova da implicacao "se n ∈ A, então n + 1 ∈ A" não garante a existência de algum elemento em A.

gabrielcguimaraes: Beleza

Lukyo: o "se..., então...." não diz nada sobre "existir n"

Lukyo: A poderia ser o conjunto vazio, e ainda assim a implicação seria válida.

gabrielcguimaraes: Então depois se supõe (e com fundamentação, já que 1 é válido) que existe um k que cumpre os respectivos requisitos, então basta provar que existe k+1 e já se resolve tudo?

Lukyo: Não provar que existe k + 1, mas provar que a implicação é válida

Lukyo: Não é a prova existencial de um elemento, sim a prova de uma implicação. Suponha n ∈ A. Com base nessa hipótese, conclua que n + 1 ∈ A.

Lukyo: Já garantimos que A não é vazio. Então podemos tomar qualquer elemento de A: "Seja n ∈ A..."

Lukyo: Daí manipule a propriedade que define o elemento de A, substituindo n por n + 1 e vai manipulando até concluir que ela também deve ser válida.

Soluções para a tarefa

Respondido por gabrielcguimaraes

Caso base $n = 1$ :
$2^{3 \cdot 1 - 1} + 3^{6 \cdot 1 - 5}\\ = 2^2 + 3^1 \\= 7\\7 \mid 7$

$n = 1$ é válido, então $A$ possui pelo menos um elemento.

Hipótese de indução: suponha que dado um $k$ qualquer, vale $7 \mid 2^{3k - 1} + 3^{6k - 5}$

Passo indutivo: provar que vale também para $k+1$ :

$2^{3 \cdot (k+1) - 1} + 3^{6 \cdot (k+1) - 5}\\=2^{3k + 3 - 1} + 3^{6k + 6 - 5}\\= 2^{3k-1} \cdot 2^3 + 3^{6k-5} \cdot 3^6\\= 2^{3k-1} \cdot 2^3 + 3^{6k-5} \cdot 3^6 + 2^3 \cdot 3^{6k-5} - 2^3 \cdot 3^{6k-5}\\= 2^3(2^{3k-1} + 3^{6k-5}) + 3^{6k-5} (3^6 - 2^3)$

Que, de acordo com a hipótese, nos permite reescrever a expressão acima como:
$= 2^3 \cdot 7q + 3^{6k-5} \cdot 721\\= 2^3 \cdot 7q + 3^{6k-5} \cdot 7 \cdot 103\\= 7(2^3 \cdot q + 3^{6k-5} \cdot 103)\\\\7 \mid 2^{3 \cdot (k+1) - 1} + 3^{6 \cdot (k+1) - 5}$

Provada a existência de pelo menos um elemento em $A$ , e que $k \in A \Longrightarrow k + 1 \in A$ , então qualquer valor natural de $k$ é válido, ou seja, $A = \mathbb{N}$ .

gabrielcguimaraes: Agora, é fundamental escrever p(k+1) com a hipótese de p(k)?

Lukyo: Use a em sua resposta com suas palavras e seja feliz :)

Lukyo: "É fundamental escrever p(k+1) com a hipótese p(k)"? Resposta: Se você estiver provando por indução, sim. Inclusive é um exercício fazer aparecer a hipótese de indução quando não é tão visível assim

gabrielcguimaraes: É para demonstrar que é uma consequência de k ser válido?

Lukyo: Sim, para mostrar que se vale p(k) então consequentemente tem que valer p(k+1).

Lukyo: Mas temos que usar a hipótese de indução: "Vale p(k)."

Lukyo: Só edite a hipótese de indução ali "existe k", na verdade é suponha que dado um k qualquer, vale p(k). A suposição não tem co consequência a existência do elemento.

Lukyo: não tem como consequência a existência do elemento. A existência do elemento (geralmente o menor elemento do conjunto pelo Princípio da Boa Ordenação), você deve verificar no caso base.

gabrielcguimaraes: Um k qualquer ou um k específico para que a condição se dê?

Lukyo: Um k qualquer maior ou igual que 1.

Respondido por fmpontes93

Demonstração:

Verifiquemos, inicialmente, se a propriedade é válida para $n = 1$ :

$7\,|\,2^{3\,.\,1-1}+3^{6\,.\,1-5}\\\\7\,|\,2^2 + 3^1 \\\\7\,|\,7.$

Como $p(1)$ , $1$ ∈ $A$ .

Admitamos $p(k)$ por hipótese, isto é:

$7\,|\,2^{3k-1} + 3^{6k-5}$

para um $k$ genérico tal que $k \geq 1$ .

Verifiquemos, por fim, se $p(k)$ implica $p(k+1):$

$7\,|\,2^{3(k+1)-1}+3^{6(k+1)-5}\\\\7\,|\,2^{3k+2}+3^{6k+1}\\\\7\,|\,2^{3}\,.\,2^{3k-1} + 3^6\,.\,3^{6k-5}\\\\7\,|\,2^{3}\,.\,2^{3k-1} + 3^6\,.\,3^{6k-5} + 3^6\,.\,2^{3k-1} - 3^6\,.\,2^{3k-1}\\\\7\,|\,3^6(2^{3k-1} + 3^{6k-5}) +2^{3k-1}(2^3-3^6).$