Ciencias computacionales

Propedeutico: Matemáticas Discretas.

INAOE

Contents
1 Inducción matemática. 2
1.1 Teorema de inducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Relaciones de Recurrencia 5
2.1 Solución de relaciones de recurrencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Método iterativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Relaciones de Recurrencia Lineales Homogéneas . . . . . . . . . . . . . . . . . . . 8

1
 Material multimedia recomendado:
Inducción:

• https://www.youtube.com/watch?v=LU88nIZXmEw
• https://www.youtube.com/watch?v=yEfz3ZsX02s
Recursión:

• https://www.youtube.com/watch?v=JHeVpfXyaB4
• https://www.youtube.com/watch?v=muRVDIhumBQ

1 Inducción matemática.
Introducción
Una técnica muy utilizada para demostrar propiedades sobre el conjunto de números naturales, es el
principio de inducción. Este principio provee una herramienta poderosa y fácil de usar por ejemplo:
¿Cuál es la fórmula de la suma de los n primeros enteros positivos impares? Las sumas de los primeros
impares positivos, para n=1,2,3,4,5, son:

1=1 1+3=4 1+3+5=9

1+3+5+7=16 1+3+5+7+9=25

A partir de estos valores, es razonable suponer que la suma de los n primeros enteros impares es n2 .
Necesitamos un método para demostrar que esta suposición es correcta, si es que realmente lo es.
La inducción matemática es una técnica que se puede utilizar para demostrar enunciados de este tipo
y de una gran variedad de objetos distintos. por ejemplo, se emplea para demostrar propiedades acerca
de la complejidad de los algoritmos, estudiar si son correctos ciertos tipos de programas de ordenador o
teoremas sobre grafos y árboles, ası́ como un amplio abanico de identidades y desigualdades.

Cabe destacar que la técnica de demostración conocida como inducción matemática está basada sobre
el principio del buen orden el cual establece que todo subconjunto X ∈ Z + contiene un entero a ∈ X
tal que a ≤ x para todo x ∈ X, es decir cualquier subconjunto no vacı́o de Z + contiene un elemento
mı́nimo por lo que el conjunto Z + es diferente a Q+ y R+ ya que solo Z + cuenta con la propiedad de
que cualquier subconjunto tiene un elemento mı́nimo.

1.1 Teorema de inducción

Ahora estableceremos las base de esta técnica de demostración por inducción.

Principio de inducción finita o principio de inducción matemática. Sea P(n) una proposición matemática
abierta (o un conjunto de tales proposiciones abiertas), en las que aparece una o varias veces la variable
n, que representa un entero positivo, tenemos que:

1) Si P(1) es verdadera; y

2) Siempre que P(k) sea verdadera (para algún k ∈ Z + ), entonces P(k+1) sera verdadera;

entonces P(n) es verdadera para todo n ∈ Z + .

Hay que tener muy en claro que P(n) es una función proposicional o un predicado como, por ejemplo,
la sentencia 1 + 2 + .... + n = n(n+1)
n o la propiedad n ≤ 2n y es por esto que la inducción matemática es

2
una técnica para demostrar esta clase de teoremas. En otras palabras, la inducción matemática se usa
para demostrar proposiciones de la forma ∀nP (n), donde el dominio es el conjunto de los enteros positivos.

Como se vio en el teorema de inducción matemática, ésta se divide en dos pasos, donde la condición
de la parte 1) se conoce como la Base de la inducción, mientras que la parte 2) se conoce como el
Paso inductivo
Nota: La sentencia P(k) para un entero positivo fijo se denomina Hipótesis de inducción.
Expresando como regla de inferencia, esta técnica de demostración se puede enunciar como sigue:

[P (1) ∧ ∀k(P (k) −→ P (k + 1))] −→ ∀nP (n)

Lo que traducido al lenguaje natural significa que, cuando se cumplen los dos pasos de inducción
matemática (Paso base P (1) y paso inductivo ∀k(P (k) −→ P (k + 1))), hemos demostrado que la
proposición P(n) es verdadera para todos los enteros positivos n (∀nP (n))

Ejemplos
Demostrar mediante el método de inducción matemática que para cualquier n ∈ Z + ,
n
X (n)(n + 1)
i = 1 + 2 + 3 + ··· + n =
i=1
2

Solución

Lo primero que se debe hacer para la demostración por el método de inducción matemática es iden-
tificar nuestra proposición P(n) por lo tanto
n
X (n)(n + 1)
P (n) = i = 1 + 2 + 3 + ··· + n = (1)
i=1
2

Una vez identificada nuestra P(n) comprobamos el paso base probando para P(1).
Paso Base.
1
X (1)(1 + 1)
P (1) = i=1= (2)
i=1
2
1
X (1)(2)
P (1) = i=1=
i=1
2
1
X 2
P (1) = i=1=
i=1
2
1
X
P (1) = i=1=1
i=1

Si el paso base es correcto, planteamos nuestra hipótesis de inducción proponiendo que n = k quedando
ası́:

Hipótesis Inductiva
P (n) = P (k)

k
X (k)(k + 1)
P (k) = i = 1 + 2 + 3 + ··· + k = (3)
i=1
2
Finalmente formulamos nuestro paso inductivo en el cual debemos demostrar que si la proposición es
válida para n = k, entonces es válida para n = k + 1. Para este paso es importante recordar que si se

3
tiene la sucesión numérica P (k) = 1 + 2 + · · · + k, la siguiente seria P (k + 1) = 1 + 2 + 3 + · · · + k + (k + 1),
puesto que hay que sumar el número que sucede a k, siendo este (k + 1) y en lo que corresponde a la
fórmula cerrada P (k) = (k)(k+1)
2 , pare el siguiente numero tendrı́amos P (k + 1) = (k+1)((k+1)+1)2 , puesto
que solo basta sustituir k por (k + 1)
Paso Inductivo.
k+1
X (k + 1)((k + 1) + 1)
P (k + 1) = i = 1 + 2 + 3 + · · · + k + (k + 1) = (4)
i=1
2
Observe como podemos sustituir la ecuación 3 en la ecuación 4, puesto que una parte de la sucesión
de P(k+1) es P(k), quedando ası́
k+1
X (k + 1)((k + 1) + 1)
P (k + 1) = i = P (k) + (k + 1) =
i=1
2

k+1
X (k)(k + 1) (k + 1)((k + 1) + 1)
P (k + 1) = i= + (k + 1) = (5)
i=1
2 2
Una vez establecido nuestro paso inductivo, sólo queda demostrar que es correcto y en este caso sólo
basta comprobar la igualdad mediante propiedades algebraicas quedando

(k)(k + 1) (k + 1)((k + 1) + 1)
+ (k + 1) =
2 2
simplificando del lado izquierdo tenemos

(k)(k + 1) + 2(k + 1) (k + 1)((k + 1) + 1)

=
2 2
Resolvemos productos
(k 2 + k) + (2k + 2) (k + 1)((k + 1) + 1)
=
2 2
efectuamos las sumas
k 2 + 3k + 2 (k + 1)((k + 1) + 1)
=
2 2
factorizamos
(k + 1)(k + 2) (k + 1)((k + 1) + 1)
=
2 2
Nota:En este último paso podemos ajustar el lado izquierdo de la ecuación descomponiendo un factor,
puesto que k + 2 = (k + 1) + 1 o efectuar la suma del lado derecho dado que (k + 1) + 1 = k + 2. Usando
la segunda opción tenemos que
(k + 1)(k + 2) (k + 1)(k + 2)
=
2 2
Lo que muestra que nuestra proposición es correcta. Puesto que P (1) es verdadera y P (k) −→ P (k+1)
(paso base e inductivo), el principio de induccion matematica muestra que p(n) es verdadera para todo
entero positivo n

4
2 Relaciones de Recurrencia
Introducción
A veces es difı́cil definir objetos explı́citamente y, sin embargo, puede resultar sencillo definiros en términos
de ellos mismos. Este proceso se llama recursión. Por ejemplo, el dibujo mostrado en la Figura 1 se
ha generado recursivamente, primero se tiene un dibujo original, luego se lleva a cabo un proceso de
superposición sucesiva de copias más pequeñas del dibujo centradas sobre el dibujo anterior.

Figure 1: Imagen recursiva extraı́da de www.rootear.com

Estas relaciones son útiles en ciertos problemas de conteo. Una relación de recurrencia relaciona el
n-ésimo elemento de una sucesión con sus predecesores. Como las relaciones de recurrencia tienen una
relación cercana con los algoritmos recursivos, éstas surgen de manera natural en el análisis de éstos.

Para clarificar las relaciones de recurrencia considere las siguientes instrucciones para generar una
sucesión:

1 Iniciar con 5.

2 Dado cualquier término, sume 3 para obtener el siguiente.

Si se listan los términos de la sucesión, se obtiene

5, 8, 11, 14, 17, .... (6)

El primer término es 5 por la instrucción 1. El segundo término es 8 porque la instrucción 2 dice que
se sume 3 a 5 para obtener el siguiente término. El tercer término es 11 porque la instrucción 2 dice que
se sume 3 a 8 para obtener el siguiente término. Si se siguen las instrucciones 1 y 2, se puede calcular
cualquier término de la sucesión. Las instrucciones 1 y 2 no dan una fórmula explı́cita para el n-ésimo
término de la sucesión en el sentido de proporcionar una fórmula en la que se pueda “sustituir n” para
obtener el valor del n-ésimo término, sino que al calcular término por término en algún momento se podrá
obtener cualquier término de la sucesión.

Si la sucesión (6) se denota por a1 , a2 , ..., se puede enunciar de nuevo la instrucción 1

a1 = 5 (7)

y la instruccion 2 se puede estableer como

an = an−1 + 3, n ≥ 2 (8)

Haciendo n = 2 en (8), se obtiene

a2 = a1 + 3

5
y por (7), a1 = 5; entonces
a2 = a1 + 3 = 5 + 3 = 8
siguiendo el mismo proceso anterior para n = 3, se obtiene

a3 = a2 + 3 = 8 + 3 = 11

Por lo tanto usando las ecuaciones 7 y 8, es posible calcular cualquier termino en la sucesión justo como
se hizo al seguir las instrucciones 1 y 2. La ecuación 8 proporciona un ejemplo de relación de recurrencia
dado que define una sucesión expresando el n-ésimo valor en termino de ciertos predecesores. Para que
una relación de recurrencia defina una sucesión, debe proporcionarse un valor o valores de ”inicio”, como
en la ecuación 7. Estos valores de inicio se llaman condiciones iniciales.

Por lo tanto podemos definir una relación de recurrencia para la sucesión a0 , a1 , · · · es una ecuación
que relaciona an con ciertos predecesores a0 , a1 , · · · , an−1 .
Las condiciones iniciales para una sucesión a0 , a1 , ... son valores dados en forma explı́cita para un número
finito de términos de la sucesión.

2.1 Solución de relaciones de recurrencia

Resolver una relación de recurrencia que implica una sucesión a0 , a1 , · · · significa encontrar una fórmula
explı́cita para el término general an . En esta sección se estudian dos métodos para resolver relaciones de
recurrencia: el de iteraciones y un método especial que se aplica a relaciones de recurrencia homogéneas
lineales con coeficientes constantes.

2.1.1 Método iterativo

Para resolver una relación de recurrencia que implica la sucesión a0 , a1 , · · · por iteración, se usa la relación
de recurrencia para escribir el n-ésimo término an en términos de algunos de sus predecesores an−1 , · · · , a0 .
Después se usa la relación de recurrencia de manera sucesiva para sustituir cada uno de an−1 , · · · por
algunos de sus predecesores.

Ejemplo 1
Resolver la siguiente relación de recurrencia mediante el método iterativo

an = an−1 + 3 (9)

sujeta a la condición inicial a1 = 2.

Sustituimos a n por n − 1 en la ecuación (9) para relacionarla con su predecesor y nos queda

an−1 = a(n−1)−1 + 3

an−1 = an−2 + 3 (10)

sustituimos la ecuación 10 en la ecuación 9 para dejarla en términos de an

an = (an−2 + 3) + 3
an = an−2 + 3 + 3
Lo que es equivalente a
an = an−2 + 2 ∗ 3 (11)
Sustituimos nuevamente n por n − 1 en la ecuación 10 para relacionarla con su siguiente predecesor

a(n−1)−1 = a(n−1)−2 + 3

an−2 = an−3 + 3 (12)

6
sustituimos la ecuación 12 en la ecuación 11 para dejarla en términos de an

an = (an−3 + 3) + 2 ∗ 3

an = an−3 + 3 + 2 ∗ 3
Lo que es equivalente a
an = an−3 + 3 ∗ 3 (13)
Observe como existe un patrón entre la ecuación 11 y 13 donde de manera general podemos decir que la
relación de recurrencia toma la forma:
an = an−k + 3k (14)
Sustituimos k por n − 1 en la ecuación 14 para dejarla en términos de la condición de inicio a1

an = an−(n−1) + 3 ∗ (n − 1)

an = a1 + 3(n − 1) (15)
Finalmente expresamos la fórmula explı́cita que describe la función de recurrencia tomando en cuenta
que a1 = 2 por la condición de inicio
an = 2 + 3(n − 1) (16)
La ecuación 16 representa de forma explı́cita la forma recursiva de la ecuación 9 dado que es la solución
a la relación de recurrencia propuesta.

Ejemplo 2
Resolver la siguiente relación de recurrencia mediante el método iterativo

sn = 2sn−1 (17)

Con condición inicial s0 = 1

Solución: Buscamos el predecesor de 17

sn−1 = 2sn−2 (18)

La dejamos en términos de n
sn = 2 ∗ 2 ∗ sn−2 (19)
buscamos el predecesor de 18
sn−2 = 2sn−3 (20)
La dejamos en términos de n
sn = 2 ∗ 2 ∗ 2 ∗ sn−3 (21)
Observando las ecuaciones 19 y 21, podemos decir que la relación de recurrencia toma la forma

sn = 2k sn−k (22)

finalmente sustituimos k por n en la ecuación 22 para dejarla en términos de la condición inicial s0 y

sustituirla, por lo tanto
sn = 2n S0

sn = 2n (23)

7
2.1.2 Relaciones de Recurrencia Lineales Homogéneas
Una relación de recurrencia homogénea lineal de orden k con coeficientes constantes es una relación de
recurrencia de la forma

an = c1 an−1 + c2 an−2 + · · · + ck an−k , ck 6= 0. (24)

donde este tipo de relación de recurrencia debe tener k condiciones iniciales

a0 = c0 , a1 = c1 , · · · , ak−1 = ck−1

En el presente documento nos centraremos en las relaciones de recurrencia lineales homogéneas con
coeficientes contantes de primero y segundo orden.

Relaciones de recurrencia lineales homogéneas de primer orden

Dada la generalización de la ecuación 24, resulta sencillo deducir que una relación de recurrencia lineal
homogénea de primer orden con coeficientes constantes es de la forma

an = can−1 (25)

y la solución a este tipo de relación de recurrencia donde n ≥ 0, c es una constante y a0 = A, es única y

está dada por

an = Acn (26)
Lo cual se puede verificar mediante el ejemplo dos (ecuación 17), el cual corresponde a una relación
de recurrencia de este tipo y se puede solucionar de manera directa según la definición anterior.

Ejemplo

Resuelva la relación de recurrencia an = 7an−1 , donde n ≥ 1 y a2 = 98

Solución
Según la definición sabemos de manera directa que nuestra relación de recurrencia toma la forma an =
a0 (7n ) sin embargo carecemos de la condición inicial a0 , pero podemos sustituirla si conocemos algún
valor para an , por ejemplo si a2 = 98

a2 = 98 = an = a0 (72 )

por lo tanto
98 = a0 (72 )
despejamos a0
a0 = 2
Quedando la forma explı́cita a la relación de recurrencia de la siguiente manera

an = 2(7n ) (27)

Relaciones de recurrencia lineales homogéneas de segundo orden

Una relación de recurrencia lineal homogénea de segundo orden con coeficientes constantes es de la
forma
an = c1 an−1 + c2 an−2 (28)
Con base en la solución de las relaciones de recurrencia de primer orden buscaremos una solución del
tipo an = ctn , que al sustituir en 28 tendremos

ctn = c1 ctn−1 + c2 ctn−2

8
Lo que al dividir toda la expresión entre ctn−2 e igualando a cero tendremos

t2 − c1 t − c2 = 0 (29)

donde 29 es una ecuación cuadrática llamada ecuación caracterı́stica, por lo que las raı́ces r1 y r2 pueden
estar en alguno de los siguientes casos a) reales y distintos, b) reales con multiplicidad dos o c)complejos
conjugados. sin embargo solo abordaremos los primeros dos casos, si se desea saber mas sobre el tercer
caso se recomienda la siguiente lectura [1, pag. 477-478]

Caso A: Raı́ces reales y distintas

Teorema: Sea
an = c1 an−1 + c2 an−2 (30)
una relación de recurrencia homogénea lineal de segundo orden con coeficientes constantes. Si S y T son
soluciones de ecuación (30), entonces U = bS + dT también es una solución de ecuación (30). Si r es una
raı́z de ecuación (29) entonces la sucesión rn , n = 0, 1, · · · , es una solución de ecuación (30). Si a es la
sucesión definida por ecuación (30),

a0 = c0 y a1 = c1

entonces existen constantes b y d tales que

an = br1n + dr2n (31)

Ejemplo
Resolver la relación de recurrencia
an = 5an−1 − 6an−2 (32)
y condiciones iniciales a0 = 7 y a1 = 16

Solución: Como sabemos que es una relación de recurrencia de orden dos podemos darle la forma
a n = tn
tn = 5tn−1 − 6tn−2
Lo que es equivalente a
t2 − 5t + 6 = 0 (33)
n n
Factorizamos y encontramos las raı́ces r1 = 2 y r2 = 3. Por lo tanto Sn = 2 y Tn = 3 y por definición si
S y T son soluciones de la relación de recurrencia, entonces bS+dT , donde b y d son números cualesquiera,
también lo son
Un = bSn + dTn

Un = b2n + d3n (34)

por lo tanto u es una solución de 32 y para satisfacer las condiciones iniciales, debe tenerse.
para la condición inicial a0
7 = U0 = b20 + d30

7=b+d (35)
para la condición inicial a1
16 = U0 = b21 + d31

16 = 2b + 3d (36)
resolvemos el sistema de ecuaciones 35 y 36. Donde b = 5 y d = 2. Finalmente sustituimos estos
resultados en la ecuación 34
Un = 5(2n ) + 2(3n ) (37)

9
Donde la ecuación 37 corresponde a la forma explı́cita de la solución de la relación de recurrencia.

Caso B: Raı́ces reales de multiplicidad dos

Teorema: Sea
an = c1 an−1 + c2 an−2 (38)
una relación de recurrencia homogénea lineal de segundo orden con coeficientes constantes. Sea a una
sucesión que satisface a ecuación (38) y
a0 = c0 y a1 = c1

Si ambas raı́ces de
t2 − c1 t − c2 = 0
son iguales a r, entonces existen constantes b y d tales que

an = brn + dnrn (39)

Ejemplo
Resolver la relación de recurrencia
an = 4(an−1 − an−2 ) (40)
y condiciones iniciales a0 = a1 = 1

Solución:
Como sabemos que es una relación de recurrencia de orden dos podemos darle la forma an = tn

tn = 4(tn−1 − tn−2 )

Lo que es equivalente a
t2 − 4t + 4 = 0 (41)
Factorizamos y encontramos las raı́ces r1 = r2 = 2. Por lo tanto nuestra solución sera del tipo

an = b2n + dn2n (42)

para satisfacer las condiciones iniciales, debe tenerse.

para la condición inicial a0 = 1
a0 = b20 + d(0)20

1=b (43)
para la condición inicial a1 = 1
a1 = b21 + d(1)21

1 = 2b + 2d (44)
Sustituimos 43 en 44 y nos queda s = − 21 , que al sustituirlo en 42

1
an = 2n − n2n
2
Sin embargo observe que esta expresión se puede simplificar pues 12 n2n es equivalente a 2−1 n2n y aplicando
reglas de los exponentes tenemos
an = 2n − n2n−1 (45)
donde la ecuación 45 es la solución explı́cita a la relación de recurrencia.

10
References
[1] R. Grimaldi, Matemáticas discreta y combinatoria: introduccián y aplicaciones. Pearson Educación,
1998.
[2] R. Johnsonbaugh and M. G. Osuna, Matemáticas discretas. Pearson Educación, 2005.
[3] K. H. Rosen and J. M. P. Morales, Matemática Discreta y sus Aplicaciones. 2004.
[4] I. S. Sominiski, El Método de la Inducción Matemática. 1990.

11