Apuntes de Matemática Discreta

Sykcc Matemática Discreta



Tema 1: Inducción y Recursión
The essential characteristic of reasoning by recurrence is that it contains,
condensed, so to speak, in a single formula, an infinity of syllogisms.
- Henri Poincaré

1. Construcción de N
Imagı́nate que el dı́a de mañana te preguntan qué son los números naturales, pero no
basta con una explicación intuituva, sino una definición formal del conjunto. ¿Cómo lo harı́as?
Los axiomas de Peano sirven para exactamente eso, con la idea pivotal de “sucesor”.

Concepto 1.1: Axiomas de Peano para definir N

1. El 0 es un número natural.

2. Todo número natural n tiene un sucesor s(n) natural.

3. ∀n ∈ N, s(n) ̸= 0
(︁ )︁
4. ∀n, m ∈ N, s(n) = s(m) → (n = m) (inyectividad de s)
(︂(︁ )︁ )︂
5. ∀A ⊆ N, (0 ∈ A) ∧ (∀n ∈ N, s(n) ∈ A) → (A = N) (Principio de Inducción)


Otras propiedades de N son:
◦ N es cerrado con respecto a las operaciones suma (+) y producto (·).

◦ Principio de Buena Ordenación (PBO): ∀A ⊆ N, A ̸= ∅, A tiene elemento mı́nimo.

◦ Definimos Nm , m ∈ N, como Nm = {n ∈ N | m ≤ n}


2. Inducción Simple sobre N y Nm
El quinto axioma es el principio de inducción matemática, que nos permite demostrar
una propiedad P sobre N:
}︄
Caso base: P (0)
−→ ∀n ∈ N, P (n)
Paso inductivo: ∀k ∈ N, P (k) → P (k + 1)

Es decir, demostramos un caso base P (0), y suponemos una hipótesis de inducción (HI)
P (k) para verificar si implica el caso de inducción (CI) P (k + 1).

En general, para m, i ∈ N: (da igual si es sobre N o Nm pues son isomorfos)

Concepto 1.2: Inducción Simple sobre Nm
}︄
Caso base: P (m), P (m + 1), . . . P (m + i)
−→ ∀n ∈ Nm , P (n)
Paso inductivo: ∀k ∈ Nm+i , P (k) → P (k + 1)




Página 1 de 9

, Sykcc Matemática Discreta

3. Inducción Completa
A veces no es suficiente suponer que el predecesor cumple la propiedad, sino todos los valores
anteriores. Esto se conoce como inducción completa, aparentemente más “fuerte”.

Concepto 1.3: Inducción Completa sobre Nm
}︄
Caso base: P (m), P (m + 1), . . . P (m + i)
(︁ )︁ −→ ∀n ∈ Nm , P (n)
Paso ind. : ∀k ∈ Nm+i−1 , ∀l ∈ Nm , l < k, P (l) → P (k + 1)



4. Construcción de Z
Análoga a la idea de sucesor, se nos puede ocurrir la idea de predecesor para definir los
números enteros. Cumple que:
◦ ∀n ∈ Z, s(p(n)) = p(s(n)) = n
◦ Z = Z+ ∪ {0} ∪ Z− , donde Z+ = {1, 2, . . . } y Z− = {−1, −2, . . . }
◦ Z es cerrado con respecto a las operaciones suma (+), resta (−) y producto (·).
◦ Z no cumple el principio de buena ordenación, pero Zm sı́.

5. Inducción Estructural sobre Z
Para Zm podemos seguir usando la inducción mostrada anteriormente, pero para Z requiere
que no solo demostremos los casos posteriores a los base, pero también los anteriores.
Esta inducción extrapolada fuera de N se le llama inducción estructural. Para Z, se puede
atacar de varias maneras. Un par de ejemplos son:

Concepto 1.4: Inducción Estructural sobre Z
⎫
Caso base: P (0) ⎪
⎪
Paso inductivo 1: ∀k ∈ Z, P (k) → P (k + 1)⎬
⎪
−→ ∀n ∈ Z, P (n)
Paso inductivo 2: ∀k ∈ Z, P (k) → P (k − 1)⎪⎪
⎪
Paso inductivo 2’: ∀k ∈ Z+ , P (k) → P (−k)
⎭




6. Recursión

Una función f : A → B está definida recursivamente si para todo x ∈ A, o bien f (x) =
y ∈ B (es un caso dado), o bien f (x) se obtiene al aplicar la regla de recurrencia un número
finito de veces junto a los casos básicos. Se pueden computar por reescritura o por iteración.
La inducción es una técnica muy útil para demostrar propiedades de funciones definidas
recursivamente. - Transparencia del profe.

Definiciones recursivas de Sumatorio y Productorio
⎧ ⎧
∑︂n ⎪
⎨ 0 si n < m n
∏︂ ⎨1
⎪ si n < m
si = sn si n = m si = sn si n = m
⎪ ⎪
i=m ⎩
sm + sm+1 + · · · + sn si m > n i=m ⎩
sm · sm+1 · . . . · sn si m > n


Página 2 de 9