Taller 2

Matemáticas discretas.
Juan Sebastián Bernal Jimenez

Diciembre primero, 2023

Prof. Francisco Albeiro Gomez Jaramillo

1
 1 Solución
1.1 Verifique que la siguiente sentencia es verdadera o
falsa:
∀n ∈ N, ∃m ∈ N : (m ≥ n) ∧ (∃r ∈ N : m = r2 )
Verificar:
Para verificar la afirmación, se considera:

Paso 1: Sea n arbitrario en N.

Paso 2: Se toma m = (n + 1)2 .

Paso 3: Se tiene que m ≥ n ya que n + 1 > n.
Paso 4: Entonces si n ∈ N, (n + 1) ∈ N ya que a cualquier número natural que se
le sume una unidad seguirá dando un número natural.

Paso 5: Desarrollando m:
(n + 1)2 = (n2 + 2n + 1) ∈ N

Obtenemos que es un cuadrado perfecto, ya que cualquier número natural

elevado al cuadrado da como resultado un número natural.
Paso 6: Se concluye con tomar (n + 1) = r, siendo r ∈ N.
Paso 7: Dado que n era arbitrario, hemos demostrado que para todo n, existe
algún m ≥ n y que además es cuadrado perfecto (VERDADERO).

1.2 Pruebe o desapruebe que:

si x ∈ R, entonces x(4 − x) ≤ 4

Verificar:
Para verificar la expresión, se considera:

Paso 1: Desarrollar la función: f (x) = 4x − x2 .

Paso 2: Cuyas raı́ces son: x = 0 y x = 4.

Paso 3: Y su vertice −(b/2a): x = 2 y y = 4.
Paso 3: Analizar función:
Siendo una cuadratica negativa, se conoce que abre hacia abajo y su vertice
serı́a el punto más alto o de mayor valor de la función, siendo ası́ que
f (x) ≤ 4 ∀x (VERDADERO).

1
 1.3 Pruebe o desapruebe que:
4n + 6n − 1 es divisible por 9 para todo número natural n ≥ 0

Verificar:
Para verificar la expresión por método de inducción, se considera:

Paso 1: Probar caso base: f (n) = 4n + 6n − 1

f (0) = 0 y f (1) = 9 (se cumplen).
Paso 2: Hipótesis inductiva (se asume para k)
f (k) = 4k + 6k − 1 (se cumple)

Es decir, 9c = 4k + 6k − 1 para c ∈ R.

Paso inductivo 1: Probar para f (k + 1) multiplicando por 4 la igualdad anterior.

36c = 4k+1 + 24k − 4
Paso inductivo 2: Sumar 3.
36c + 3 = 4k+1 + 24k − 1

Paso inductivo 3: Restar 18k.

36c + 3 − 18k = 4k+1 + 6k − 1
Paso inductivo 3: Sumar 6.
36c + 9 − 18k = 4k+1 + 6k + 6 − 1 = 4k+1 + 6(k + 1) − 1

Paso inductivo 4: 4k+1 +6(k+1)−1 es de la misma forma que la hipótesis inductiva. Además,
36c+9−18k se puede escribir de la forma 9(4c+1−2k), razones suficientes
para demostrar satisfactoriamente la expresión inicial.

1.4 Pruebe o desapruebe que:

52n+1 + 22n+1 es divisible por 7 para todo número natural n ≥ 0

Verificar:
Para verificar la expresión por método de inducción, se considera:

Paso 1: Probar caso base: f (n) = 52n+1 + 22n+1

f (0) = 7 y f (1) = 133 = 19 ∗ 7 (se cumplen).
Paso 2: Hipótesis inductiva (se asume para k)
f (k) = 52k+1 + 22k+1 = 7c (se cumple).

Paso inductivo 1: Probar para f (k + 1) = 52(k+1)+1 + 22(k+1)+1 = 52k+3 + 22k+3 .

Paso inductivo 2: = 52 ∗ 52k+1 + 22 ∗ 22k+1 = 25 ∗ 52k+1 + 4 ∗ 22k+1

2
Paso inductivo 3: = 4 ∗ 52k+1 + 4 ∗ 22k+1 + 21 ∗ 52k+1
Paso inductivo 4: = 4(52k+1 + 22k+1 ) + 21 ∗ 52k+1
Paso inductivo 5: Por hipótesis inductiva tenemos que 52k+1 + 22k+1 = 7c entonces
Paso inductivo 6: = 4 ∗ 7c + 21 ∗ 52k+1 = 7(4c + 3 ∗ 52k+1 )
Donde (4c + 3 ∗ 52k+1 ) es un número natural. Por lo tanto se demuestra
la expresión inicial.

1.5 Pruebe o desapruebe que:

n
2 +1 es divisible por 3 para todo número entero impar n ≥ 0

Verificar:
Para verificar la expresión por método de inducción, se considera:

Paso 1: Probar caso base: f (n) = 2n + 1

f (1) = 3 y f (3) = 9 (se cumplen).
Paso 2: Hipótesis inductiva (se asume para k sabiendo n = 2k + 1)
f (k) = 2k + 1 = 3c
f (k) = 22k+1 + 1 = 3c (se cumple).
Paso inductivo 1: Probar para f (k + 1) = 22(k+1)+1 + 1.
Paso inductivo 2: = 22k+3 + 1
Paso inductivo 3: = 4 ∗ 22k+1 + 1
Paso inductivo 4: = 2 ∗ 22k+1 + 1
Paso inductivo 5: Por hipótesis inductiva tenemos que 22k+1 + 1 = 3c entonces
Paso inductivo 6: = 2 ∗ 3c Donde un multiplo de 3 mulitplicado por cualquier natural da
como resultado un mulitplo de 3, demostrando el enunciado inicial.

1.6 Pruebe o desapruebe que:

12 + 32 + 52 + ... + (2n − 1)2 = (4n3 − n)/3

Para verificar la expresión por método de inducción, se considera:

Paso 1: Probar caso base: f (n) = 2n + 1

12 = 1 y 12 + 32 = (32 − 2)/3 = 10 (se cumplen).
Paso 2: Hipótesis inductiva (se asume para k
12 + 32 + 52 + ... + (2k − 1)2 = (4k 3 − k)/3.

3
Paso inductivo 1: Probar para (k+1):
12 + 32 + 52 + ... + (2k − 1)2 + (2(k + 1) − 1)2 = (4k 3 − k)/3.
Paso inductivo 2: = Por hipótesis de inducción tenemos que
12 + 32 + 52 + ... + (2k − 1)2 = (4k 3 − k)/3.

Paso inductivo 3: = (4k 3 − k)/3 + (2(k + 1) − 1)2 .

Paso inductivo 4: = (4k 3 − k)/3 + (2k + 1)2 .
Paso inductivo 5: = (4k 3 − k)/3 + 4k 2 + 4k + 1.
Paso inductivo 6: = (4k 3 − k + 12k 2 + 12k + 3)/3.

Paso inductivo 7: = ((k + 1)(4k 2 + 8k + 3))/3.

Paso inductivo 8: = (4(k + 1)(k + 1)2 − (k + 1))/3.
Paso inductivo 8: = (4(k+1)3 −(k+1))/3 Que es de la misma forma de la hipótesis inductiva,
demostrando el enunciado.

1.7 Pruebe o desapruebe que:

Sea fn el n-esimo número de Fibonacci, pruebe que fn y fn+1 son primos rela-
tivos para todo n ≥ 1

Para verificar la expresión por método de contradicción, se considera:

Paso 1: Primeros casos Fibonacci: f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5,

f6 = 8....

Paso 2: Coomparar casos f5 = 5, f6 = 8

f5 y f6 NO son primos relativos, ya que 8 no es número primo. Por lo
tanto la expresión inicial queda DESPROBADA.

1.8 Pruebe o desapruebe que:

n n
√ √
1+ 5 1− 5
Vamos a demostrar que Fn = a √+b
5
, donde a = 2 yb= 2 , para todo
n ≥ 0.
Paso Base (n = 0 y n = 1):

a0 + b0 2
F0 = √ =√
5 5
√
1+ 5
√ √
a1 + b1 2 + 1−5
1 5
F1 = √ = √ 2 =√ =
5 5 5 5

Ambos casos coinciden con los valores conocidos de los números de Fibonacci.

4
 Hipótesis Inductiva: Supongamos que la afirmación es cierta para n = k
y n = k + 1, es decir:
ak + bk ak+1 + bk+1
Fk = √ , Fk+1 = √
5 5
Paso Inductivo: Queremos demostrar que la afirmación también es cierta
para n = k + 2.
Fk+2 = Fk+1 + Fk
ak+1 + bk+1 ak + bk
= √ + √
5 5
1 k+1 k+1
+ ak + bk


=√ a +b
5
Usamos las definiciones de a y b para simplificar:
1  √ √ 
Fk+2 = √ Fk+1 · 5 + Fk · 5
5

Fk+2 = Fk+1 + Fk
Hemos demostrado que Fk+2 = Fk+1 + Fk , que es la relación de recurrencia
de los números de Fibonacci.
n n
Por lo tanto, hemos demostrado por inducción que Fn = a √+b 5
para todo
n ≥ 0.

1.9 Pruebe o desapruebe que:

Existe un número infinito de primos

Para verificar la proposición por reducción al absurdo, se considera:

Paso 1: Axioma: Todo número natural mayor que 1 es divisible por algún número
primo por el teorema fundamental de la aritmética.
Paso 2: Suponer que el conjunto de números primos es finito:
P = {p1 , p2 , p3 . . . , pn }.

Paso 3: Suponer numero M como el producto de todos los números primos más 1:
M = p1 ∗ p2 ∗ p3 .... + 1.

Paso 4: M no es divisible por ningún primo, puesto que el residuo siempre es uno
(Contradicción con axioma)
Paso 5: Contradicción al suponer que es un conjunto finito. El conjunto de números
primos es entonces infinito.

5
 1.10 Pruebe o desapruebe que:
La raı́z cúbica de 2 es un número irracional

Para verificar la proposición por reducción al absurdo, se considera:

Paso 1: Se
√ supone a la raı́z cúbica de 2 como racional
3
2 = a/b con a y b enteros positivos sin factores primos comunes.
Paso 2: Elevar al cubo:
2 = a3 /b3 .

Paso 3: Resolver:
b3 ∗ 2 = a3 .
Obteniendo que a3 es par. Por consiguiente a es par y es de la forma a=2k
con k en los enteros.

Paso 4: Resolver para b:

8k 3 = b3 .
Paso 5: LLegamos a una contradicción, ya que a y b no pueden tener factores
primos comunes, como en este caso es el número 2. Por contradicción se
demuestra que la raı́z cúbica de 2 es irracional.

1.11 Pruebe o desapruebe que:

Para todos los números reales x y y , si x es racional y y es irracional, entonces
x + y es irracional.

Para verificar la proposición por reducción al absurdo, se considera:

Paso 1: Se supone que la suma nos da racional

x = m/n, y = b emtonces m/n + b = a/c

Paso 2: Resolviendo:
b = a/c − m/n = (an − mc)/cn.
En la cual todos los terminos son enteros positivos.
Paso 3: Llegamos a una contradicción ya que y es irracional, pero nos dio como
resultado un número racional, es decir, la fración entre dos enteros. Como
el supuesto es absurdo, queda demostrado que la suma entre un racional
y un irracional siempre es irracional.

6
 1.12 Verdadero o falso (justifique):
1.12.1 Para cada número real positivo x , si x es irracional entonces
x2 es irracional.
√
FALSO. Simplemente hayamos un contraejemplo, que en este caso va a ser 2,
el cual es irracional. Al elevarlo al cuadrado resulta el número 2, que claramente
tiene forma racional (2/1).

1.12.2 Para
√ cada número real positivo x , si x es irracional entonces
x es irracional.
VERDADERO. Para verificar la proposición por reducción al absurdo, se con-
sidera:

√
√ sabe que x ∈ I y se asume que x es racional ∈ Q .
Paso 1: Se
x = a/b con a y b en los enteros.
Paso 2: Resolviendo:
x = a2 /b2 y b2 ∗ x = a2 .

Paso 3: Llegamos a dos contradicciones: de la primera ecuación tenemos que un

entero al cuadrado es entero, que divido sobre un entero me sigue dando
entero, pero por el enunciado sabemos que x no es entero sino irracional;de
la segunda tenemos que un irracional multiplicado por un entero da como
resultado un entero, siendo esto el segundo absurdo, ya que el resultado
es irracional.

Paso 4: Por reducción al absurdo queda comprobado que si x es irracional, su raı́z

cuadrada también lo es.

1.13 Pruebe o desapruebe que:

√ √
Para cada número real x , x + 2 es irracional, o −x + 2 es irracional.

Para verificar la proposición por contrapositiva, se considera:

√
Paso 1: Expresar en lógica proposicional:
√ Si x es un número real, entonces x + 2
es irracional, o −x + 2 es irracional.
√ √
Paso 2: Contrapositiva: Si x + 2 y −x + 2 son racionales, entonces x no es un
número real.

7
Paso 3: Suponemos
√ que las expresiones
√ son racionales:
x + 2 = a/b y −x + 2 = c/d con a & b y c & d ∈ Z .
Paso 4: Despejando
√ a ambos
√ lados la raı́z:
2 = a/b − x y 2 = c/d + x .

Paso 5: Resolviendo:
c/d + x = a/b − x y x = (ad − cb)/2bd, es decir x ∈ Q.
Paso 6: Y volviendo
√ a cualquiera de√las dos suposiciones √
iniciales:
x+ 2 = a/b entonces 2=√ a/b−x, es decir 2 = a/b−(ad−cb)/2bd.
Obteniendo como resultado que 2 ∈ Q, siendo esto un absurdo ya que
en realidad es un número irracional

Paso 7: Analizar: √ √
Se tiene que para x + 2 y −x + 2 ∈ Q , entonces de entre todos los
numeros reales, x solo puede tomar valores en el conjunto de los
√ numeros
racionales x ∈ Q. Pero al ser racional se llega al absurdo que 2 ∈ Q.

Paso 8: Conclusión:
Se concluye que x ∈/ Q, pero esa es la única posibilidad de que x ∈ R, por
consiguiente concluimos que x ∈/ R.
Paso 9: Devolver la contrapositiva: √ √
Demostrando que cuando x + 2 y −x + 2 ∈ Q entonces x ∈
/
R, es equivalente a demostrar la proposición lógica inicial del paso 1.
(VERDADERO)

1.14 Pruebe o desapruebe que:

Para cada número entero n , n es par si y solo si 4 divide a n4

Para verificar la proposición se comprueban ambos condicionales:

Paso 1: Probar: si n es par, entonces n4 = 4c:

Se supone n par, de la forma n = 2k con k en los enteros. Entonces
reemplazando
(2k)4 = 16k 4 y 16 siempre es divisible por 4 entonces se comprueba. (Se
cumple)
Paso 2: Probar: si n4 = 4c, entonces n es par:
Se supone n4 = 4c, y se supone también n = 2k + 1 n impar con k en los
enteros. Entonces reemplazando
(2k+1)4 = 16k 4 +32k 3 +24k 2 +8k+1 y esto es absurdo porque (2k+1)4 =
16k 4 + 32k 3 + 24k 2 + 8k + 1 ̸= 4c, ya que cualquier número par más una
unidad da impar, por consiguiente no divisible por 4.

8
Paso 3: Como el supuesto deriva en un absurdo, necesariamente n debe ser par
para que se cumpla n4 = 4c. (Se cumple).
Paso 4: Como ambas condicionales se cumplen, se verifica el condicional. (Verifivado)

1.15 Pruebe o desapruebe que:

Para cada entero a , si a2 = a , entonces a = 0 o a = 1.

Para verificar la proposición por comprobación de todos los casos, se consid-

era:

Paso 1: Para a = 0, 02 = 0 (Se cumple).

Paso 2: para a2 = a en los enteros, podemos dividir por a obteniendo: a = 1(Se
cumple).

Paso 3: Para todo el resto de casos no se cumple y basta con ver el comportamiento
de la función cuadrática.

1.16 Pruebe o desapruebe que:

No existen números naturales a y n con n ≥ 2 y a2 + 1 = 2n .
Para verificar la proposición se considera evaluar por casos:

Paso 1: Resolviendo: a2 = 2n − 1.

Paso 2: Caso n es par: 2n es un cuadrado perfecto. En este caso no hay ninguna

raı́z entera para ningún número natural inmediatamente anterior a un
cuadrado perfecto, a excepción del 1 pero no entra en el ejercicio.
√
Paso 3: Caso n es impar: 2n es de la forma x ∗ 2 para x par, lo cual es un número
irracional. Por definición, si un número es irracional, su raı́z cuadrada
también lo será, por consiguiente la única opción es que a sea irracional.
Lo anterior contradice la proposición inicial que a y n son naturales.
Paso 4: Queda demostrado que no existen a y n naturales tal que se cumpla la
condición inicial. (Se cumple que no existen).

1.17 Pruebe o desapruebe por inducción que la función

funciona:
Paso 1: Caso base sum(A, 0) = 0 (Se cumple).
Paso 2: Hipótesis inductiva, se supone para k:
sum(A, 0) = A0 + A1 + ...Ak

9
 Figure 1: Codigo

Paso 3: Paso inductivo, probar para k + 1:

sum(A, k + 1) = A0 + A1 + ...Ak + Ak+1 .
Paso 3: Por hipotesis inductiva tenemos: sum(A, k + 1) = sum(A, k) + Ak+1 =
sum(A, k + 1) (Probado por inducción).

10