Capítulo 4
Inducción y Recursividad
4.1 Inducción Matemática
La inducción matemática es un método de demostración que se aplica sobre los conjuntos
de los números enteros positivos o el de los números naturales.
Principio de inducción matemática
Sea P (n) una propiedad que se define para enteros n y sea a un entero fijo. Suponga que
los siguientes dos enunciados son verdaderos:
1. P (a) es verdadera. (Paso base de la inducción).
2. Para todo entero k ≥ a, si P (k) es verdadera entonces P (k + 1) es verdadera.
Entonces, el enunciado
para todo entero n ≥ a, P (n)
es verdadero.
Ejemplo 4.1 Probar que para n ≥ 1 se verifica que
∑
n
n (n + 1) (n + 2)
i (i + 1) =
i=1
3
Ejemplo 4.2 Probar que para n ≥ 3 se verifica que n2 > 2n.
∑
n 3n2 − n
Ejemplo 4.3 Demostrar por inducción que (3k − 2) = para todo n ∈ Z+ .
k=1 2
Ejemplo 4.4 Utilice inducción para demostrar que 7n − 1 es divisible entre 6 para toda n ≥ 0.
Ejemplo 4.5 Demostar que P (n) = 2 + 4 + 6 + 8 + ... + 2n = n(n + 1), para todo n ∈ Z+ .
Ejemplo 4.6 Probar que P (n) = 2n < n! para todo n ∈ Z+ , n ≥ 4.
4.2 Principio de Inducción matemática fuerte
Sea P (n) una propiedad que se define para n enteros y sean a y b enteros fijos con a ≤ b.
Suponga que los siguientes dos enunciados son verdaderos:
1. P (a), P (a + 1), ...y P (b) son todas verdaderas. (Paso básico.)
2. Para cualquier número entero k ≥ b, si P (i) es verdadera para todo entero i de a hasta
k, entonces P (k + 1) es verdadera. (Paso inductivo.)
Entonces el enunciado
para todo entero n ≥ a, P (n),
es verdadero. (La suposición de que P (i) es verdadera para todo entero i desde a hasta k se llama
la hipótesis inductiva. Otra forma de indicar la hipótesis inductiva es decir, que P (a), P (a +
1), ..., P (k) son todas verdaderas.)
Ejemplo 4.7 Demostrar que cualquier número entero mayor que 1 es divisible por un número
primo.
Ejemplo 4.8 Demostrar por inducción que todo número mayor o igual que 8 se puede expresar
como la suma de números tres y cincos.
Ejemplo 4.9 Demuestre que para cualquier entero n ≥ 1, si x1 , x2 , ..., xn son n números, en-
tonces no importa cómo se insertan los paréntesis en su producto, el número de multiplicaciones
que se utilizan para calcular el producto es n − 1.
Ejemplo 4.10 Se define una sucesión s0 , s1 , s2 , ... de la siguiente manera: s0 = 0, s1 = 4, sk =
6sk−1 − 5sk−2 para todo entero k ≥ 2.
a. Encuentre los cuatro primeros términos de esta sucesión
b. Se afirma que para cada entero n ≥ 0, el enésimo término de la sucesión tiene el mismo
valor que el dado por la fórmula 5n − 1. En otras palabras, la afirmación es que todos los
términos de la sucesión satisfacen la ecuación sn = 5n − 1. Demuestre que esta es verdadera.
4.3 El principio del buen orden para enteros
El principio del buen orden para enteros se ve muy diferente de los comunes y sólidos
principios de la inducción matemática, pero se puede demostrar que los tres principios son
equivalentes. Es decir, si cualquiera de los tres es verdadero, entonces también lo son los otros
dos.
4.3.1 Principio del buen orden para los enteros
Sea S un conjunto de números enteros que contienen uno o más números enteros todos los
cuales son mayores que un entero fijo. Entonces S tiene un elemento mínimo.
En términos generales, se dice que un conjunto ordenado S está bien ordenado si cualquier
subconjunto de S contiene un primer elemento. Así, el principio del buen orden establece que
N está bien ordenado.
Se dice que un conjunto S de enteros está acotado por abajo si todo elemento de S es mayor
que algún entero m (que puede ser negativo). El número m se denomina cota inferior de S.
S : x2 , x 5 , x 1 , x 3 , x 4 , x 6 , . . . , x n
existe en m ∈ Z tal que m < x2
Ejemplo 4.11 Utilice el principio del buen orden para probar el algoritmo de división. Recuerde
que el algoritmo de división establece que si a es un número entero y d es un número entero
positivo, entonces existen enteros únicos q y r con 0 ≤ r < d y a = dq + r.
Otra consecuencia del principio del buen orden es el hecho de que cualquier sucesión es-
trictamente decreciente de números enteros no negativos es finita. Es decir, si r1 , r2 , r3 , ... es
una sucesión de números enteros no negativos que satisfacen ri ≥ ri+1 para toda i ≥ 1, en-
tonces r1 , r2 , r3 , ... es una sucesión finita. Este hecho es frecuentemente usado en ciencias de
la computación para demostrar que los algoritmos terminan después de un número finito de
pasos.
2
4.4 Definiciones recursivas e Inducción estructural
A veces es difícil definir un objeto explícitamente. Sin embargo, puede resultar fácil definir
este objeto en términos de sí mismo. Este proceso se llama recursividad.
Podemos usar la recursividad para definir sucesiones, funciones y conjuntos. En la mayoría
de los cursos de matemáticas elementales, los términos de una sucesión se especifican mediante
una fórmula explícita.
Veamos la siguiente sucesión: a1 = 2, a2 = 10, a3 = 50, a4 = 250, . . .. Por la forma que
aparecen los términos, si escribimos
a1 = 2 = 50 × 2
a2 = 5 × 2 = 10 = 51 × 2
a3 = 5 × 10 = 50 = 5 × 5 × 2 = 52 × 2
a4 = 5 × 50 = 5 × 5 × 5 × 2 = 53 × 2
..
.
ak = 5 × ak−1
..
.
entonces, podemos definir la sucesión, estableciendo que
a1 = 2
an = 5 · an−1 , para n ≥ 2
Cuando se hace esto, se dice que la sucesión se ha definido en forma recursiva. También podemos
usar la inducción para probar los resultados sobre la sucesión.
4.4.1 Conjuntos definidos recursivamente
Para definir un conjunto de objetos de forma recursiva, se identifica un número de objetos
básicos que forman parte del conjunto y se dan las reglas que muestran cómo construir nuevos
elementos a partir de los anteriores. Más formalmente, una definición recursiva de un conjunto
tiene las siguientes tres componentes:
I. Base: Un enunciado de que ciertos objetos pertenecen al conjunto.
II. Recursión: Un conjunto de reglas que indican cómo formar nuevos conjuntos de objetos
de un conjunto a partir de los que ya se sabe que están en el conjunto.
III. Restricción: Un enunciado de que no haya objetos que pertenezcan al conjunto distintos
de los que provienen de I y II.
Un conjunto no vacío y finito Σ de símbolos se conoce como alfabeto. Por ejemplo el alfabeto
castellano que está conformado por 28 símbolos. Cada símbolo de un alfabeto es una cadena
sobre dicho alfabeto Una secuencia finita de símbolos de un determinado alfabeto se conoce
como palabra sobre dicho alfabeto (frecuentemente se usa el término cadena para no confundir
palabra como una secuencia ordenada de símbolos del alfabeto).
La cadena vacía o nula, ε, es una secuencia vacía de símbolos.
Ejemplo 4.12 Longitud de una cadena Dar una definición recursiva de l(a), la longitud de la
cadena a.
Ejemplo 4.13 El conjunto de cadenas sobre un alfabeto Σ. Considere el conjunto S de todas
las cadenas en a y b. S se define recursivamente de la siguiente manera:
I. Base: ε está en S, donde ε es la cadena nula.
3
II. Recursión: Si s ∈ S, entonces
a.)sa ∈ S y b.)sb ∈ S,
donde sa y sb son las concatenaciones de s con a y b, respectivamente.
III. Restricción: No hay nada en S que no sean los objetos definidos en I y II.
Deduzca el hecho de que ab ∈ S.
Ejemplo 4.14 Sea Sn el número de subconjuntos de un conjunto de n elementos. Como al
pasar de un conjunto de (n − 1) elementos a un conjunto de n elementos se duplica el número
de subconjuntos, se obtiene la relación de recurrencia Sn = 2Sn−1 . La condición inicial es
S0 = 1.
Ejemplo 4.15 Sea Sn el número de cadenas de n bits que no contienen el patrón 111. Desarrolle
la relación de recurrencia para S1 , S2 , ... y las condiciones iniciales que definen la sucesión S.
Ejemplo 4.16 La función factorial f : N → R se puede definir recursivamente por: f (0) = 1,
y f (n) = n × f (n − 1) para toda n > 0.
Ejemplo 4.17 La sucesión de números de Catalan, llamada así por el matemático belga Eugène
Catalan (1814-1894), aparece en una notable variedad de contextos diferentes en matemáticas
discretas. Se puede definir de la siguiente manera: para cada natural n > 1,
( )
1 2n
Cn = .
n+1 n
a. Encuentre C1 , C2 y C3 .
4k − 2
b. Muestre que esta sucesión satisface la relación de recurrencia Ck = Ck−1 para todo
k+1
natural k ≥ 2.
Ejemplo 4.18 La sucesión de Fibonacci, importante en la teoría de grafos, se define por la
relación de recurrencia: f0 = 1, f1 = 1, f2 = 2, y fn = fn−1 + fn−2 , n ≥ 3. Demuestre que
fk = 3fk−3 + 2fk−4 para todo entero k ≥ 4.
4.4.2 Inducción estructural
Para probar resultados sobre conjuntos definidos de forma recursiva, utilizamos un método
llamado inducción estructural.
Una prueba por inducción estructural consta de dos partes.
Paso Base: Demostrar que el resultado es válido para todos los elementos especificados en
el paso de base de la definición recursiva para estar en el conjunto.
Paso Recursivo: Mostrar que si el enunciado es verdadero para cada uno de los elementos
usados para construir elementos nuevos en el paso recursivo de la definición, el resultado es
válido para estos nuevos elementos.
La validez de la inducción estructural se deriva del principio de inducción matemática
para los enteros no negativos. Para verlo, suponemos que P (n) establece que la afirmación es
verdadera para todos los elementos del conjunto que son generados por n o menos aplicaciones de
las reglas en el paso recursivo de una definición recursiva. Habremos establecido que el principio
de inducción matemática implica el principio de inducción estructural si podemos demostrar
que P (n) es verdadero siempre que n es un número entero positivo. En el paso básico de una
prueba por inducción estructural, mostramos que P (0) es verdadero. Es decir, mostramos que
el resultado es verdadero para todos los elementos especificados para estar en el conjunto en el
4
paso básico de la definición. Una consecuencia del paso recursivo es que si asumimos que P (k)
es verdadero, se sigue que P (k + 1) es verdadero. Cuando hemos completado una demostración
usando inducción estructural, hemos demostrado que P (0) es verdadero y que P (k) implica
P (k + 1). Por inducción matemática se deduce que P (n) es verdadero para todos los enteros
n no negativos. Esto también muestra que el resultado es verdadero para todos los elementos
generados por la definición recursiva, y muestra que la inducción estructural es una técnica de
prueba válida.
Ejemplo 4.19 Estructuras paréntesis
Ciertas configuraciones de paréntesis en expresiones algebraicas son “legales” [tales como
(())() y ()()()], mientras que otras no lo son [tales como )())) y ()))(((]. Esta es una definición
recursiva para generar el conjunto P de la ”configuración legal” de paréntesis.
I. Base: () está en P .
II. Recursión:
a. Si E está en P , por lo que es (E).
b. Si E y F están en P , por lo que es EF .
III. Restricción: No hay configuraciones de paréntesis que estén en P que no sean las
derivadas de I y II.
Demuestre que todas las configuraciones en P contienen un número igual de paréntesis
izquierdo y derecho.
Ejemplo 4.20 En el ejemplo del conjunto de cadenas sobre un alfabeto Σ, demostrar por
inducción estructural que l (ab) = l (a) + l (b), donde a, b ∈ S.
4.5 Algoritmos recursivos
Una función recursiva (seudocódigo) es una función que se llama a sí misma. Un algorit-
mo recursivo es un algoritmo que contiene una función recursiva. La recursión es una forma
poderosa, elegante y natural de resolver una clase amplia de problemas.
Ejemplo 4.21 Cálculo del factorial de n
Este algoritmo recursivo calcula n!.
Entrada: n, un entero mayor o igual que 0
Salida: n!
factorial(n)
if (n ≥ 0)
return 1
return n*factorial(n - 1)
}
Vemos cómo funciona el algoritmo para varios valores de n. Si n = 0 la función da como
salida el valor 1. Si n = 1 la salida es n · (n − 1)! = 1 · 0! = 1 · 1 = 1. Si n = 2, se procede
a la línea 4 ya que n ̸= 0. Se emplea esta función para calcular 1! Acabamos de ver que la
función calcula 1 como el valor de 1! En la línea 4, la función calcula correctamente el valor de
2!: n · (n − 1)! = 2·1! = 2·1 = 2.
Si n = 3 se procede a la línea 4 ya que n ̸= 0. Se utiliza esta función para calcular 2!.
Acabamos de ver que la función calcula 2 como el valor de 2!. En la línea 4, la función calcula
correctamente el valor de 3!: n · (n − 1)! = 3 · 2! = 3 · 2 = 6.
Implementación del algoritmo factorial de n en Python
5
Ejemplo 4.22 Cálculo del factorial de n
def factorial(n):
””” Precondición: n entero >=0.
Devuelve: n! ”””
if n == 0:
return 1
return n * factorial(n-1)
Un algoritmo para el cálculo de an implementado en Python.
Primero hay que considerar que
n n
an = a 2 · a 2 , si n es par
n−1 n−1
an = a 2 ·a 2 · b, si n es impar
Ejemplo 4.23 Cálculo de la potencia n de a
def potencia(a,n):
””” Precondición: n debe ser mayor o igual que cero.
Devuelve: a^n. ”””
# Caso base
if n <= 0:
return 1
# n par
if n % 2 == 0:
pot = potencia(a, n/2)
return pot * pot
# n impar
else:
pot = potencia(a, (n-1)/2)
return pot * pot * a
Veamos como funciona el algoritmo.
>>> potencia(2,10)
1024
>>> potencia(3,3)
27
>>> potencia(5,0)
1
El orden de las llamadas, haciendo un seguimiento simplificado de la función será:
1. potencia(2,10)
2. pot = potencia(2,5) b :2, n:10
3. pot = potencia(2,2) b :2, n:5
4. pot = potencia(2,1) b :2, n:2
5. pot = potencia(2,0) b :2, n:1
6. return 1 b :2, n:0
7. return 1 * 1 * 2 b :2, n:1, pot:1
8. return 2 * 2 b :2, n:2, pot:2
9. return 4 * 4 * 2 b :2, n:5, pot:4
10. return 32 * 32 b :2, n:10, pot:32
Podemos ver, entonces, que para calcular 210 se realizaron 5 llamadas a potencia.
6
Ejemplo 4.24 Ordenamiento por mezcla
El objetivo de este algoritmo es tomar un arreglo de elementos a[r], a[r + 1], . . . , a[s] (en
donde r ≤ s) para ordenarlo. El arreglo de salida se denota por a[r], a[r + 1], . . . , a[s], que tiene
los mismos valores que el arreglo de entrada, pero en orden ascendente. El arreglo de entrada
se divide en dos subarreglos de aproximadamente la misma longitud, cada uno de los cuales es
ordenado usando ordenamiento por mezcla. Entonces los dos subarreglos son mezcla entre sí.
Entrada: r y s [enteros positivos con r < s] a[r], a[r + 1], . . . , a[s] (un arreglo de objetos
datos que se pueden ordenar)
inf := r, sup := s
while (inf < sup)
med:=⌊ inf +2 sup ⌋
llame a ordenamiento por mezcla con entrada inf, med y
a[inf ], a[inf + 1], … , a[med]
llame a ordenamiento por mezcla con entrada med + 1, sup y
a[med + 1], a[med + 2], … , a[sup]
(Después de que se han completado estos pasos, los arreglos a[inf], a[inf + 1], … , a[med]
y a[med + 1], a[med + 2], … , a[sup] quedan ordenados.)
mezclar a[inf], a[inf + 1], … , a[med] y
a[med + 1], a[med + 2], … , a[sup]
(Este paso se puede hacer con una llamada a un algoritmo de mezcla. Para poner el arreglo
final en orden ascendente, el algoritmo de mezcla se debe escribir para tomar dos arreglos en
orden ascendente y mezclarlos en un arreglo en orden ascendente].)
end while
Salida: a[r], a[r + 1], … , a[s] (un arreglo con los mismos elementos como el arreglo de
entrada pero en orden ascendente)
Implementación del ordenamiento por mezcla con Python.
Para tal efecto necesitamos hacer lo siguiente.
Diseñamos la función merge_sort(lista):
1. Si lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer. Se
devuelve lista tal cual.
2. De lo contrario:
a) medio = len(lista)/2
b) izq = merge_sort(lista[:m])
c) der = merge_sort(lista[m:])
d) Se devuelve merge(izq, der).
A continuación diseñamos la función merge que realiza la intercalación ordenada de dos
listas ordenadas (dadas dos listas ordenadas se debe obtener una nueva lista que resulte de
intercalar a ambas de manera ordenada).
Diseñamos la función merge(lista1, lista2):
1. Utilizaremos dos índices, i y j, para recorrer cada una de las dos listas.
2. Utilizaremos una tercera lista, resultado, donde almacenaremos el resultado.
3. Mientras i sea menor que el largo de lista1 y j menor que el largo de lista2, significa que
hay elementos para comparar en ambas listas.
a) Si el menor es el de lista1:
1) Agregar el elemento i de lista1 al final del resultado.
2) Avanzar el índice i.
b) de lo contrario:
1) Agregar el elemento j de lista2 al final del resultado.
2) Avanzar el índice j.
7
4. Una vez que una de las dos listas se termina, simplemente hay que agregar todo lo que
queda en la otra al final del resultado.
El código resultante del diseño de ambas funciones es el siguiente.
Ejemplo 4.25 Ordenamiento por mezcla
1 #!/usr/bin/env python
2 #encoding: latin1
3
4 def merge_sort(lista):
5 ””” Ordena lista mediante el método merge sort.
6 Pre: lista debe contener elementos comparables.
7 Devuelve: una nueva lista ordenada. ”””
8
9 # Una lista de 1 o 0 elementos, ya está ordenada
10 if len(lista) < 2:
11 return lista
12 # Si tiene 2 o más elementos, se divide al medio y ordena cada parte
13 medio = len(lista) / 2
14 izq = merge_sort(lista[:medio])
15 der = merge_sort(lista[medio:])
16 return merge(izq, der)
17
18 def merge(lista1, lista2):
19 ””” Intercala los elementos de lista1 y lista2 de forma ordenada.
20 Pre: lista1 y lista2 deben estar ordenadas.
21 Devuelve: una lista con los elementos de lista1 y lista2. ”””
22
23 i, j = 0, 0
24 resultado = []
25
26 # Intercalar ordenadamente
27 while(i < len(lista1) and j < len(lista2)):
28 if (lista1[i] < lista2[j]):
29 resultado.append(lista1[i])
30 i += 1
31 else:
32 resultado.append(lista2[j])
33 j += 1
34
35 # Agregar lo que falta, si i o j ya son len(lista) no agrega nada.
36 resultado += lista1[i:]
37 resultado += lista2[j:]
38
39 return resultado.
4.6 Corrección de programas
Cada programa está diseñado para realizar una tarea específica: para calcular la media o la
mediana de un conjunto de números, calcular la cantidad de los cheques de pago de la nómina
de una empresa, reorganizar los nombres en orden alfabético, etc.
8
Diremos que un programa es exacto si produce la salida especifica en la documentación
adjunta para cada conjunto de base de datos del tipo especificado en la documentación.
La mayoría de los programadores escriben sus programas mediante una combinación de
análisis lógico de ensayo y error. Para obtener que un programa corra todo, el programador
debe corregir todos los errores de sintaxis. Sin embargo, cuando se han eliminado los errores
de sintaxis, el programa todavía puede contener errores lógicos que impidan que se produzca el
resultado correcto.
Con la mayoría de las técnicas que aún están en el proceso de desarrollo, los métodos para
probar la exactitud del programa son un poco incómodos y difíciles de manejar.
Se dice que un programa es correcto si produce la salida correcta para cada entrada posible.
Una prueba de que un programa es correcto consta de dos partes. La primera muestra que
se obtiene la respuesta correcta si el programa finaliza. Esta parte de la prueba establece la
corrección parcial del programa. La segunda parte de la demostración muestra que el programa
siempre termina.
Para especificar lo que significa que un programa produzca una salida correcta, se utili-
zan dos declaraciones. La primera es la aserción inicial o pre-condiciones, que proporciona las
propiedades que deben tener los valores de entrada. La segunda es la declaración final o post-
condiciones, que da las propiedades que debería tener la salida del programa, si el programa
hizo lo que se pretendía. Deben proporcionarse declaraciones de apertura y cierre apropiadas
al verificar un programa.
Ejemplo 4.26 Algoritmo de pre-condiciones y post-condiciones
Se presentan pre y post condiciones para algunos algoritmos comunes.
a. Algoritmo para calcular un producto de enteros no negativos
Pre-condición: Las variables de entrada m y n son números enteros no negativos.
Post-condición: La variable de salida p es igual a mn.
b. Algoritmo para encontrar el cociente y el residuo de la división de un entero positivo entre
otro
Pre-condición: Las variables de entrada a y b son enteros positivos.
Post-condición: Las variables de salida q y r son enteros tales que a = bq + r y 0 ≤ r ≤ b.
Una prueba de la exactitud del algoritmo consiste en mostrar que si la precondición para el
algoritmo es verdadera para un conjunto de valores de las variables de entrada y si se ejecutan
los enunciados de los algoritmos, entonces, la post-condición también es verdadera.
4.6.1 Invariantes de bucle
El método de los invariantes de bucle se utiliza para demostrar la exactitud de un bucle
con respecto a ciertas pre y post condiciones. Se basa en el principio de inducción matemática.
Supongamos que un algoritmo contiene un bucle while y que la entrada a este bucle está
restringida por una condición G, llamada la guarda. Supongamos también que las afirmaciones
que describen el estado actual de las variables del algoritmo se han colocado inmediatamente
antes e inmediatamente después del bucle. La afirmación justo antes del bucle se llama la
precondición para el bucle y el justo después se llama la post-condición para el bucle. El bucle
escrito tiene la forma siguiente:
(Pre-condición para el bucle)
while (G)
(Enunciados en el cuerpo del bucle.
Ninguno contiene enunciados de ramificación
que lleven fuera del bucle.)
end while
9
(Post-condición para el bucle)
Un bucle se define como exacto con respecto a su pre y post-condiciones, si y sólo si, cada
vez que las variables del algoritmo satisfacen la precondición para el bucle y el bucle termina
después de un número finito de pasos, las variables del algoritmo satisfacen la post-condición
para el bucle.
El establecimiento de la exactitud de un bucle utiliza el concepto de invariante del bucle.
Una invariante del bucle es un predicado con dominio en un conjunto de enteros, lo que satisface
la condición: Para cada iteración del bucle, si el predicado es verdadero antes de la iteración, es
verdadero después de la iteración. Además, si el predicado satisface las siguientes dos condiciones
adicionales, el bucle será correcto con respecto a las pre-y postcondiciones:
1. Es verdadero antes de la primera iteración del bucle.
2. Si el bucle termina después de un número finito de iteraciones, la veracidad del invariante
del bucle garantiza la veracidad de la post-condición del bucle.
Teorema 4.27 Teorema del invariante del bucle
Sea un bucle while con guarda G dada, junto con pre y post-condiciones que son predicados
en las variables del algoritmo. También sea un predicado I(n), llamado el invariante del bucle,
se le dará. Si las cuatro propiedades son verdaderas, entonces el bucle es correcto con respecto
a sus pre y post-condiciones.
1. Propiedad básica: La pre-condición para el bucle implica que I(0) es verdadera antes
de la primera iteración del bucle.
2. Propiedad inductiva: Para todo entero k ≥ 0, si la guarda G y el invariante del bucle
I(k) son verdaderos antes de una iteración del bucle, entonces I(k + 1) es verdadera
después de la iteración del bucle.
3. Posible falsedad de la guarda: Después de un número finito de iteraciones del bucle,
la guarda G se convierte en falsa.
4. Exactitud de la post-condición: Si N es el menor número de iteraciones después de
que G es falsa e I(N ) es cierto, entonces los valores de las variables algoritmo será tal
como se especifica en la post-condición del bucle.
Ejemplo 4.28 Exactitud de un bucle para calcular un producto
El siguiente bucle está diseñado para calcular el producto mx para un entero no negativo m
y un número real x, sin utilizar una operación de multiplicación incorporada. Antes del bucle,
las variables i y productos se han introducido y dan los valores iniciales de i = 0 y producto =
0.
(Pre-condición: m es un entero no negativo, x es un número real, i = 0 y el producto = 0.)
while (i ̸= m)
1. producto: producto + x
2. i := i + 1
end while
(Post-condición: producto = mx)
Sea el invariante del bucle
I(n) : i = n y el producto = nx
La condición de guarda G del bucle while es
G : i ̸= m
Utilice el teorema del invariante del bucle para probar que el bucle while es correcto con respecto
a la propuesta de las pre y post-condiciones.
10
4.6.2 Reglas de inferencia
Una útil regla de inferencia prueba que un programa es correcto dividiendo el programa en
una secuencia de subprogramas y luego mostrando que cada subprograma es correcto.
Supongamos que el programa S se divide en subprogramas S1 y S2 . Hagamos S = S1 ; S2
para indicar que S está formado por S1 seguido de S2 . Supongamos que se ha establecido la
corrección de S1 con respecto a la afirmación inicial p y la afirmación final q, y la corrección
de S2 con respecto a la afirmación inicial q y la afirmación final r. De esto se deduce que si p
es verdadero y S1 se ejecuta y termina, entonces q es verdadero; y si q es verdadero, y S2 se
ejecuta y termina, entonces r es verdadero. Por tanto, si p es verdadero y S = S1 ; S2 se ejecuta
y termina, entonces r es verdadero. Esta regla de inferencia, llamada regla de composición,
puede enunciarse como
p{S1 }q
q{S2 }r
∴ p{S1 ; S2 }r.
Veremos algunas reglas de inferencia para segmentos de programa que involucran declara-
ciones condicionales y bucles. Debido a que los programas se pueden dividir en segmentos para
pruebas de corrección, esto nos permitirá verificar muchos programas diferentes.
Declaraciones condicionales
Primero, se darán reglas de inferencia para enunciados condicionales. Suponga que un seg-
mento de programa tiene la forma
si la condición entonces
S
donde S es un bloque de declaraciones. Entonces se ejecuta S si la condición es verdadera,
y no se ejecuta cuando la condición es falsa. Para verificar que este segmento es correcto con
respecto a la aserción inicial p y la aserción final q, se deben hacer dos cosas. Primero, debe
demostrarse que cuando p es verdadera y la condición también es verdadera, entonces q es
verdadera después de que S termina. En segundo lugar, debe demostrarse que cuando p es
verdadera y la condición es falsa, entonces q es verdadera (porque en este caso S no se ejecuta).
Esto conduce a la siguiente regla de inferencia
(p ∧ condición){S}q
(p ∧¬condición) → q
∴ p{si condición entonces S}q.
Ejemplo 4.29 Verificar que el segmento de programa
if x > y entonces
y : =x
es correcto con respecto a la afirmación inicial T y la afirmación final y ≥ x.
De manera similar, supongamos que un programa tiene una declaración de la forma
if condición then
S1
else
S2
11
Si la condición es verdadera, entonces S1 se ejecuta; si la condición es falsa, S2 se ejecuta.
Para verificar que este segmento de programa es correcto con respecto a la afirmación inicial p
y la afirmación final q, se deben hacer dos cosas. Primero, debe demostrarse que cuando p es
verdadera y la condición es verdadera, entonces q es verdadera después de que S1 termina. En
segundo lugar, debe demostrarse que cuando p es verdadera y la condición es falsa, entonces q
es verdadera después de que S2 termina. Esto conduce a la siguiente regla de inferencia
(p ∧ condición){S}q
(p ∧¬condición) → q
∴ p{si condición entonces S1 else S2 }q.
Ejemplo 4.30 Verificar que el segmento de programa
if x < 0 then
abs:= -x
else
abs:=x
es correcto con respecto a la afirmación inicial T y la afirmación final abs = |x|.
{
−x, si x < 0
|x| =
x, si x ≥ 0
4.7 Ejercicios
1. Probar que para n ≥ 1 se verifica que
∑
n
n (n + 1) (n + 2)
i (i + 1) =
i=1
3
2. Probar que para n ≥ 1 se verifica que n2 > 2n.
3. Probar que para n ≥ 6 se verifica que n! > n3 .
4. Sea x un número real, x > −1. Demostrar que se cumple que (1 + x)n ≥ 1 + nx para
todo número natural n.
5. Demostrar que para todo n ∈ N se verifica que 20 + 21 + · · · + 2n = 2n+1 − 1.
∑
n 3n2 − n
6. Demostrar por inducción que (3k − 2) = para todo n ∈ Z+ .
k=1 2
n(5n − 3)
7. Demostrar que para todo entero n ≥ 1, 1 + 6 + 11 + 16+···+(5n − 4) = .
2
4(4n − 16)
8. Demostrar que para todo entero n ≥ 3, 43 + 44 + 45 + · · · + 4n = .
3
9. Demostrar que para cada entero n ≥ 0, 7n − 1 es divisible por 6.
10. Demostrar que 1 + 3n < 4n , para cada entero n ≥ 0.
11. Una sucesión a1 , a2 , a3 , ... se define haciendo a1 = 3 y ak = 7ak−1 para todo entero k ≥ 2.
Demuestre que an = 3 · 7n−1 para todo entero n ≥ 1.
12
12. Se define una sucesión s0 , s1 , s2 , ... de la siguiente manera: s0 = 0, s1 = 4, sk = 6ak−1 −
5ak−2 para todo entero k ≥ 2.
a. Encuentre los cuatro primeros términos de esta sucesión.
b. Se afirma que para cada entero n ≥ 0, el enésimo término de la sucesión tiene el mismo
valor que el dado por la fórmula 5n − 1. En otras palabras, la afirmación es que todos
los términos de la sucesión satisfacen la ecuación sn = 5n − 1. Demuestre que esta es
verdadera.
(Usar inducción fuerte)
13. Supongamos que f0 , f1 , f2 , ... es una sucesión definida de la siguiente manera: f0 = 5, f2 =
16, fk = 7fk−1 − 10fk−2 para todo entero k ≥ 2. Demuestre, usando inducción fuerte, que
fn = 3 · 2n + 2 · 5n para todo entero n ≥ 0.
14. Los ejercicios que siguen contienen un bucle while y un predicado. En cada caso demuestre
que si el predicado es verdadero antes de la entrada al bucle, entonces también lo es
después de la salida del bucle.
(a) bucle: while (m ≥ 0 y m ≤ 100)
m := m + 1
n := n - 1
end while
predicado: m + n = 100
(b) bucle: while (m ≥ 0 y m ≤ 100)
m := m + 4
n := n - 2
end while
predicado: m + n es impar
(c) bucle: while (m ≥ 0 y m ≤ 100)
m := 3·m
n := 5·n
end while
predicado: m3 > n2
(d) bucle: while (n ≥ 0 y n ≤ 100)
n := n + 1
end while
predicado: 2n < (n + 2)!
(e) bucle: while (n ≥ 3 y n ≤ 100)
n := n + 1
end while
predicado: 2n + 1 ≤ 2n .
15. Cada uno de los ejercicios que siguen contiene un bucle while escrito con una pre y una
post-condición y también un invariante del bucle. En cada caso, utilice el teorema del
invariante del bucle para demostrar la exactitud del bucle con respecto a las pre y a las
post condiciones.
13
(a) [Precondición: m es un entero no negativo, x es un número real, i = 0 y exp = 1.]
while (i ̸= m)
1. exp := exp · x
2. i := i + l
end while
[Post-condición: exp = xm ]
invariante del bucle: I (n) es “exp = xn e i = n”.
(b) [Precondición: mayor = A[1] y i = 1]
while (i ̸= m)
1. i := i + 1
2. if A[i] > mayor then mayor := A[i]
end while
[Post-condición: mayor = valor máximo de A[1], A[2], . . . , A[m].]
invariante del bucle: I (n) es “mayor = valor máximo de A[1], A[2], . . . , A[n + 1]
e i = n + 1”.
(c) [Precondición: suma = A[1] e i = 1]
while (i ̸= m)
1. i := i + 1
2. suma := suma + A[i]
end while
[Post-condición: suma = A[1] + A[2] + . . . + A[m]]
invariante del bucle: I(n) es “i = n + 1 y suma = A[1] +A[2] + . . . + A[n + 1]”.
(d) [Pre-condición: a = A y A es un número entero positivo.]
while (a > 0)
1. a := a - 2
end while
[Post-condición: a = 0 si A es par y a = - 1 si A es impar.]
invariante del bucle: I (n) es “Tanto a como A son enteros pares o ambos son enteros
impares y a ≥ - 1”.
16. Sea a0 , a1 , a2 , ... definida por la fórmula an = 3n + 1, para todo entero n ≥ 0. Demuestre
que esta sucesión satisface la relación de recurrencia ak = ak−1 + 3, para todo entero
k ≥ 1.
17. Sea b0 , b1 , b2 , ... definida por la fórmula bn = 4n , para todo entero n ≥ 0. Demuestre que
esta sucesión satisface la relación de recurrencia bk = 4bk−1 , para todo entero k ≥ 1.
( de los)números de Catalan, demuestre que para todo entero n ≥ 1,
18. Para la sucesión
1 2n + 2
Cn = .
4n + 2 n+1
19. Para la sucesión de Fibonacci, demuestre fk = 3fk−3 + 2fk−4 para todo entero k ≥ 4.
20. Para la sucesión de Fibonacci, utilice inducción matemática fuerte para probar que fn <
2n para toda n ≥ 1.
21. Un palíndromo es una cadena que se lee igual de izquierda a derecha que al revés. Describa
un algoritmo para determinar si una cadena de n caracteres es un palíndromo. (Por
ejemplo, anitalavalatina).
14
