Provas por Contradição e Indução

  

As provas por contradição e prova por indução são dois métodos importantes em matemática para demonstrar a veracidade de uma proposição. Cada um tem suas características e é mais adequado a certos tipos de teoremas.

---

1. Prova por Contradição (ou Redução ao Absurdo) 🔴

A prova por contradição é uma forma de prova indireta. Nesse método, supomos que a proposição que queremos provar seja falsa e mostramos que essa suposição leva a uma contradição lógica. Como uma proposição não pode ser falsa e verdadeira ao mesmo tempo, concluímos que nossa suposição inicial está errada, e, portanto, a proposição original deve ser verdadeira.

Passos para Prova por Contradição:

1. Assumir que a proposição é falsa.
2. Derivar uma contradição a partir dessa suposição, ou seja, chegar a uma situação impossível ou absurda.
3. Concluir que a proposição original deve ser verdadeira, pois a suposição de que ela era falsa levou a um absurdo.

Exemplo de Prova por Contradição:

Proposição: A raiz quadrada de 2 não é um número racional.

Prova:

1. Suponha que a raiz quadrada de 2 seja um número racional. Logo, podemos escrevê-la como $r = \frac{p}{q}$, onde $p$ e $q$ são inteiros sem fatores comuns (a fração está simplificada).
2. Logo, temos a equação $r^2 = 2$, ou seja: $$\left( \frac{p}{q} \right)^2 = 2 \quad \Rightarrow \quad \frac{p^2}{q^2} = 2 \quad \Rightarrow \quad p^2 = 2q^2$$
3. Isso significa que $p^2$ é um número par (pois é múltiplo de 2).
4. Se $p^2$ é par, então $p$ deve ser par (pois o quadrado de um número ímpar é ímpar).
5. Então, podemos escrever $p = 2k$, onde $k$ é um número inteiro.
6. Substituindo $p = 2k$ na equação $p^2 = 2q^2$, temos: $$(2k)^2 = 2q^2 \quad \Rightarrow \quad 4k^2 = 2q^2 \quad \Rightarrow \quad 2k^2 = q^2$$
7. Isso significa que $q^2$ também é par, e, portanto, $q$ também deve ser par.
8. No entanto, se $p$ e $q$ são ambos pares, isso contradiz nossa suposição inicial de que $p$ e $q$ não têm fatores comuns (já que ambos seriam divisíveis por 2).
9. Portanto, nossa suposição de que a raiz quadrada de 2 é racional leva a uma contradição.

Conclusão: A raiz quadrada de 2 não é um número racional.

---

2. Prova por Indução Matemática 🔢

A prova por indução é um método utilizado principalmente para demonstrar proposições envolvendo sequências ou séries e que são válidas para todos os números naturais (ou um subconjunto deles). A indução matemática é uma técnica poderosa que funciona de forma análoga ao princípio da indução.

Passos para Prova por Indução:

1. Base da indução: Provar que a proposição é verdadeira para o menor valor de $n$ (geralmente $n = 1$).
2. Passo indutivo: Assumir que a proposição é verdadeira para um valor arbitrário $n = k$ e então provar que, sob essa hipótese, ela é verdadeira para $n = k+1$.
3. Conclusão: Concluir que a proposição é verdadeira para todos os valores de $n$ maiores ou iguais ao valor base.

Exemplo de Prova por Indução:

Proposição: Para todo número natural $n$, temos que $1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$.

Prova:

1. Base da indução: Verifique para $n = 1$:

   $$1 = \frac{1(1 + 1)}{2} = \frac{1(2)}{2} = 1$$

   Portanto, a proposição é verdadeira para $n = 1$.

2. Passo indutivo: Agora, suponha que a proposição seja verdadeira para $n = k$, ou seja:

   $$1 + 2 + 3 + \dots + k = \frac{k(k + 1)}{2}$$

   Agora, mostramos que a proposição também é verdadeira para $n = k+1$. Ou seja, precisamos provar que:

   $$1 + 2 + 3 + \dots + k + (k + 1) = \frac{(k+1)(k+2)}{2}$$

   Usando a hipótese de indução, sabemos que:

   $$1 + 2 + 3 + \dots + k = \frac{k(k + 1)}{2}$$

   Então, adicionamos $k + 1$ a ambos os lados:

   $$\frac{k(k + 1)}{2} + (k + 1) = \frac{k(k + 1)}{2} + \frac{2(k + 1)}{2} = \frac{(k + 1)(k + 2)}{2}$$

   Isso é exatamente o que queríamos provar para $n = k + 1$.

3. Conclusão: Como a base da indução e o passo indutivo foram comprovados, pela indução matemática, a proposição é verdadeira para todo número natural $n$.

---

Diferenças Principais:

Prova por Contradição	Prova por Indução
Parte do pressuposto de que a proposição é falsa e busca uma contradição.	Prova a proposição para um caso base e, em seguida, demonstra que, se for válida para um $n = k$, ela também será válida para $n = k+1$.
Usada quando uma proposição leva a um absurdo lógico.	Usada para demonstrar teoremas que se aplicam a todos os números naturais ou conjuntos infinitos.

---

Conclusão:

• A prova por contradição é útil quando é difícil ou impossível provar uma proposição diretamente, mas se assume a negação dela e chega-se a um absurdo.
• A prova por indução é uma ferramenta poderosa para demonstrar proposições envolvendo números naturais ou sequências infinitas, onde a validação para um valor implica a validação para todos os valores subsequentes.