2 Técnicas de demostración ‣ Part I Fundamentos y el principio de inducción ‣ Matemática discreta

2.1 Demostracion directa

La demostración directa consiste en probar la tesis directamente a partir de la hipótesis.

Theorem 2.1.

Si $n$ es un numero entero $n\geq 1$ , entonces $n^{2}+n$ es par.

Proof 2.2.

Si $n$ es un numero entero $n\geq 1$ , hay dos casos:

1.

Si $n$ es par, se puede expresar como $n=2m$ con $m\in\mathbb{Z}$ . Así, tenemos:

$n^{2}+n=(2m)^{2}+2m=4m^{2}+2m=\underbrace{2(2m^{2}+m)}_{\text{numero par}}$
2.

Si $n$ es impar, se puede expresar como $n=2m+1$ con $m\in\mathbb{Z}$ . Así,

${}n^{2}+n=(2m+1)^{2}+(2m+1)=4m^{2}+4m+1+2m+1=\\ {}=4m^{2}+6m+2=\underbrace{2(2m^{2}+3m+1)}_{\text{numero par}}$

2.2 Demostración por contraposición

Si queremos demostrar por contrarreciproco el teorema $A\implies B$ basta con demostrar el teorema $\neg B\Rightarrow\neg A$ generalmente usando la técnica de demostración directa. Es decir, probamos que lo contrario de la tesis implica lo contrario de la hipótesis.

Theorem 2.3.

Si $n$ es un numero entero de forma que $n^{2}$ es impar, entonces $n$ es impar.

Proof 2.4.

Lo demostraremos por contraposición.

Supongamos que $n$ es un número par. Entonces $n=2c,\,c\in\mathbb{Z}$ . Sustituyendo,

n^{2}=(2c)^{2}=4c^{2}=2(2c^{2})

Luego $n^{2}$ también es un número par. Como $\neg B\Rightarrow\neg A$ , se cumple el teorema que queríamos demostrar.

2.3 Demostracion por reduccion al absurdo

Si queremos demostrar por reduccion al absurdo el teorema $A\Rightarrow B$ basta con que supongamos que se cumpla la hipotesis $(A)$ y lo contrario de la tesis (no B). Si suponemos que se cumple a la vez $A$ y no $B$ haciendo deducciones llegamos a que algo es imposible.

Theorem 2.5.

Si $n$ es un numero entero de forma que $n^{2}$ es par, entonces $n$ es par.

Proof 2.6.

Lo demostraremos por reduccion al absurdo. Supongamos que se cumple que $n^{2}$ es par y $n$ es impar.

Como $n$ es impar, entonces $n=2c+1,\;c\in\mathbb{Z}$ y llegamos a

n^{2}=(2c+1)^{2}=4c^{2}+4c+1=\underbrace{2(2c^{2}+c)+1}_{\text{numero impar}}

Luego $n^{2}$ es impar, pero por hipótesis hemos supuesto que $n^{2}$ es par. Ningún número es impar y par a la vez, por lo que hemos llegado a una contradiccion.

Así tenemos que, si se cumple que $n^{2}$ es par, entonces obligatoriamente se cumple que $n$ es par.

Theorem 2.7.

Existe una cantidad infinita de numeros primos.

Proof 2.8.

En primer lugar, reescribimos el teorema: Si $A$ es el conjunto de todos los numeros primos, entonces su cardinal es infinito.

Lo demostramos por reduccion al absurdo. Suponemos que $A$ es el conjunto de todos los numeros primos y que este conjunto es finito.

Como $A$ es finito el conjunto de todos los numeros primos es $A=\left\{p_{1},p_{2},\ldots,p_{n}\right\}$ . Ahora tomamos

x=1+p_{1}p_{2}\cdot\ldots\cdot p_{n}

$x$ es un numero entero (suma y producto de numeros enteros) y no puede ser un numero primo porque es mayor que todos los numeros que pertenecen a $A$ ya que si tomamos $p_{j}$ en $A$ :

x=1+\underbrace{p_{1}p_{2}}_{\geq 1}\cdot\ldots\cdot p_{j}\cdot\ldots\cdot% \underbrace{p_{n}}_{\geq 1}\geq 1+p_{j}>p_{j}

Ademas, $x$ no es divisible por ninguno de los primos. Supongamos que $x$ es divisible por $p_{1}$ . Entonces

x=cp_{1}=1+p_{1}p_{2}\cdots p_{n}\Rightarrow 1=cp_{1}-p_{1}p_{2}\cdots p_{n}=p% _{1}(c-p_{2}\cdots p_{n})

Por tanto, 1 es múltiplo de $p_{1}$ . Esto es imposible, pues el $1$ solo es múltiplo de si mismo. Esto se repite para el resto de los numeros del conjunto $A$ .

Es decir, $x$ es un numero entero que no es primo y tampoco es divisible por ningun numero primo. Como es imposible, llegamos a que el conjunto de los numeros primos no puede ser finito.

2.4 Contraejemplos

Los contraejemplos no son un método de demostración, sino una técnica para demostrar que un teorema es falso.

Basta con encontrar un caso particular (contraejemplo) en el que se cumplen las hipotesis pero no la tesis para probar que el teorema es falso.

Example 2.9.

Pierre de Fermat conjeturó en 1650 que todos los numeros de la forma $F_{n}=2^{2^{n}}+1$ son primos, cosa que es cierta si $n=0,1,2,3$ y $4$ , pero Leonard Euler demostró que si $n=5$ , el numero resultante no es primo. Asi, se demostró que la conjetura anterior era falsa.