Práctico 1
Matemática Discreta I – Año 2021/1
FAMAF
(1) Demostrar las siguientes afirmaciones, donde a, b, c y d son siempre números
enteros. Justificar cada uno de los pasos en cada demostración indicando el
axioma o resultado que utiliza.
a) a = −(−a)
b) a = b si y sólo si −a = −b
c) a + a = a implica que a = 0.
(2) Idem (1).
a) 0 < a y 0 < b implican 0 < a · b
b) a < b y c < 0 implican b · c < a · c
(3) Probar las siguientes afirmaciones, justificando los pasos que realiza.
a) Si 0 < a y 0 < b entonces a < b si y sólo si a2 < b2 .
b) Si a 6= 0 entonces a2 > 0.
c) Si a 6= b entonces a2 + b2 > 0.
d) Si a + c < b + c entonces a < b.
(4) Calcular evaluando las siguientes expresiones:
X4 Y5
a) r b) i
r=0 i=1
−1
n
X 7
Y
c) d)
1
k=−3
k(k + 4) n=2
n−1
(5) Calcular:
a) 210 − 29 b) 32 25 − 35 22
n n
c) (22 )n − (2n )2 d) (22 + 1)(22 − 1)
(6) Dado un natural m, probar que ∀n ∈ N; x, y ∈ R, se cumple:
a) x n · x m = x n+m b) (x · y)n = x n · yn c) (x n )m = x n·m
(7) Analizar la validez de las siguientes afirmaciones:
n k n+k
a) (22 )2 = 22 , n, k ∈ N.
b) (2n )2 = 4n , n ∈ N.
c) 27+11 = 27 + 211 .
Pn
(8) Probar que i=0 2i = 2n+1 − 1 (n ≥ 0).
1
2
(9) Demostrar por inducción las siguientes igualdades:
n
X n
X Xn
a) (ak + bk ) = ak + bk , n ∈ N.
k=1 k=1 k=1
n
X n(n + 1)
b) j= , n ∈ N, n ∈ N.
j=1
2
n
X n(n + 1)(2n + 1)
c) i2 = , n ∈ N.
i=1
6
n 2
X n(n + 1)
d) i =
3
, n ∈ N.
i=1
2
n
X
e) (2k + 1) = (n + 1)2 , n ∈ N0 .
k=0
n
X an+1 − 1
f) ak = , donde a ∈ R, a 6= 0, 1, n ∈ N0 .
k=0
a−1
(10) Hallar n0 ∈ N tal que ∀n ≥ n0 se cumpla que n2 ≥ 11n + 3.
(11) Sea {un }n∈N la sucesión definida por recurrencia como sigue: u1 = 3, u2 = 5
y un = 3un−1 − 2un−2 con n ∈ N, n ≥ 3. Probar que un = 2n + 1, para todo
n ∈ N.
(12) Sea {un }n∈N la sucesión definida por recurrencia como sigue: u1 = 9, u2 = 33,
un = 7un−1 − 10un−2 , ∀n ≥ 3. Probar que un = 2n+1 + 5n , para todo n ∈ N.
(13) Sea {an }n∈N0 la sucesión definida recursivamente por
a0 = 1,
a = 1,
1
an = 3an−1 + (n − 1)(n − 3)an−2 , para n ≥ 2.
Probar que an = n! para todo n ∈ N0 .
(14) Sea {an }n∈N0 la sucesión definida recursivamente por
a0 = 0,
a = 7,
1
an = 5an−1 + 6an−2 , para n ≥ 2.
Probar que an = 6n + (−1)n+1 para todo n ∈ N0 .
Pn−1
(15) Sea un definida recursivamente por: u1 = 2, un = 2 + i=1 2n−2i ui ∀ n > 1.
a) Calcule u2 y u3 .
b) Proponga una fórmula para el término general un y pruébela por inducción.
3
(16) Las siguientes proposiciones no son válidas para todo n ∈ N. Indicar en qué
paso del principio de inducción falla la demostración:
a) n = n2 , b) n = n + 1, c) 3n = 3n+2 , d) 33n = 3n+2 .
§ Ejercicios de repaso. Los ejercicios marcados con (∗)
son de mayor dificultad.
(17) Demostrar por inducción las siguientes igualdades:
n
Y i+1
a) = n + 1, n ∈ N.
i=1
i
n
X n
b) , n ∈ N.
1
−1
=
i=1
4i2 2n + 1
n
! n
X X
c) i2 / j = , n ∈ N.
2n + 1
i=1 j=1
3
n
Y n+1
d) 1− 2 , n ∈ N y n ≥ 2.
1
i
=
i=2
2n
e) Si a ∈ R y a ≥ −1, entonces (1 + a)n ≥ 1 + n · a, ∀ n ∈ N.
n n
!2
X X
f) Si a1 , . . . , an ∈ R, entonces a2k ≤ |ak | , n ∈ N.
k=1 k=1
g) Si a1 , . . . , an ∈ R y 0 < ai < 1∀ i, entonces (1 − a1 ) · · · (1 − an ) ≥ 1 − a1 −
· · · − an , n ∈ N.
(18) Sea {an }n∈N la sucesión definida recursivamente por
a1 = 1,
a = 2,
2
an = (n − 2)an−1 + 2(n − 1)an−2 , para n ≥ 3.
Probar que an = n! para todo n ∈ N.
(19) Sea {an }n∈N0 la sucesión definida recursivamente por
a0 = 0,
a = 5,
1
an = an−1 + 6an−2 , para n ≥ 2.
Probar que an = 3n + (−1)n+1 2n para todo n ∈ N0 .
(∗)
(20) Encuentre el error en los siguientes argumentos de inducción.
a) Demostraremos que 5n + 3 es múltiplo de 5 para todo n ∈ N.
Supongamos que 5k + 3 es múltiplo de 5, siendo k ∈ N. Entonces existe
p ∈ N tal que 5k + 3 = 5p. Probemos que 5(k + 1) + 3 es múltiplo de 5:
4
Como
5(k + 1) + 3 = (5k + 5) + 3 = (5k + 3) + 5 = 5p + 5 = 5(p + 1),
entonces obtenemos que 5(k + 1) + 3 es múltiplo de 5. Por lo tanto, por
el principio de inducción, demostramos que 5n + 3 es múltiplo de 5 para
todo n ∈ N.
b) Sea a ∈ R, con a 6= 0. Vamos a demostrar que para todo entero no
negativo n, an = 1.
Como a0 = 1 por definición, la proposición es verdadera para n = 0.
Supongamos que para un entero k, am = 1 para 0 ≤ m ≤ k. Entonces
k ak
ak+1 = aak−1 = 1·1
1
= 1. Por lo tanto, el principio de inducción fuerte implica
n
que a = 1 para todo n ∈ N.
(21) (∗)
La sucesión de Fibonacci se define recursivamente de la siguiente manera:
u1 = 1, u2 = 1, un+1 = un + un−1 , n ≥ 2.
Los primeros términos de esta sucesión son: 1, 1, 2, 3, 5, 8, 13, . . .
Demostrar por inducción que el término general de esta sucesión se puede
√ !n √ !n #
calcular mediante la fórmula
"
1− 5
un = √ − .
1 1+ 5
5 2 2
√ √
(Ayuda: usar que 2
y 1−2 5 son las raíces de la ecuación cuadrática x 2 −
1+ 5
√ n+1 √ n √ n−1
x − 1 = 0 y por lo tanto 1±2 5 = 1±2 5 + 1±2 5 ).
(22) Probar las siguientes afirmaciones usando inducción en n:
a) n2 ≤ 2n para todo n ∈ N, n > 3 .
b) ∀n ∈ N, 3n ≥ 1 + 2n .
