Introducción
Definición 1
Llamaremos sucesión de números a toda función u : N → R.
E JEMPLO : 1 an = n.
2 bn = n1 .
3 cn = sen( 2π
n
).
4 un = 2n .
O BSERVACIÓN : En el ejemplo anterior, las sucesiones bn y cn toman números naturales y de-
vuelven números reales que no siempre pertenecen a los naturales. En cambio, las imágenes de
las sucesiones an y un viven en N.
Distinción entre sucesión recursiva y explícita
Si observamos con detenimiento las sucesiones del ejemplo anterior, notamos que todas ellas
tienen una expresión algebraica explícita. es decir, todas ellas dependen del valor n y sus imá-
genes se pueden calcular sólo considerando el valor n.
Sin embargo, la sucesión un admite otra expresión, a la que llamaremos recursiva. Si bien se
trata de otra expresión algebraica, ésta no depende solamente del valor que toma n, sino del
valor (o valores) previos de la sucesión.
En el caso de la sucesión un podríamos definirla de la siguiente manera:
((
2 si n = 1
un =
2un−1 si n ≥ 2.
En esta última definición, para calcular el término n-ésimo de la sucesión un es necesario
conocer el término anterior de la misma, y por ello se denomina recursiva, porque recurre a los
valores previos para calcular el siguiente.
No es difícil advertir que la expresión recursiva de una sucesión tiene un costo computacional
añadido, puesto que para conocer un valor de la sucesión antes hemos de calcular los valores
previos, remitiéndonos siempre hasta el comienzo de la sucesión.
En nuestro ejemplo, u2 = 2u1 = 22 = 4. Luego u3 = 2u2 = 2 · 24 = 23 = 8. Luego
u4 = 2u3 = 2 · 23 = 24 = 16.
Es fácil observar en este caso que se trata de la sucesión geométrica de razón 2, por lo que
podemos obtener una expresión algebraica que no depende de los valores previos de la sucesión,
sino sólo de la variable n.
Un desafío de la matemática es encontrar expresiones algebraicas cerradas (que sólo depen-
den de la variable n) para describir sucesiones recursivas. Otro de los grandes desafíos que
planteamos en inducción es corrobar que una expresión cerrada coincide con la expresión ex-
presión recursiva de una sucesión dada.
Aplicación del principio de inducción
E JERCICIO 1: Sea la sucesión definida de forma recursiva como
((
1 Si n = 1;
un = 2n−1
2 2n+1 un−1 si n ≥ 2.
Probar que
1 2n
un = , ∀n ∈ N.
n+1 n
O BSERVACIÓN : En este caso tenemos una sucesión un definida de forma recursiva y tenemos un
candidato f (n) a ser la fórmula cerrada de dicha sucesión.
Puesto en estos términos, queremos
1 2n
corroborar que un = f (n), allí donde f (n) = n+1 n
. Como queremos esto para todos los
naturales, la prueba se funda en el principio de inducción.
Resolución
Paso base Queremos ver que si n = 1, entonces la expresión cerrada coincide con el valor
que toma el primer término de la sucesión un .
Para ello, veamos por un lado que
1 2·1 1
f (1) = = 2 = 1.
1+1 1 2
Por otro lado, por su misma definición, el primer término de la sucesión es u1 = 1.
Así pues, obtuvimos que u1 = f (1). Esto nos permite avanzar hacia el paso inductivo.
Paso inductivo
Supongamos que ∃k ∈ N tal que uk = f (k). Ésta es nuestra hipótesis inductiva: que en
algún k natural (con k ≥ 2), la sucesión recursiva coincide con la fórmula cerrada que estamos
buscando corroborar.
En otras palabras, con la hipótesis inductiva asumimos que
1 2k
uk = .
k+1 k
Es conveniente, antes de comenzar la prueba, escribir a dónde queremos llegar para observar
en cada paso de la prueba qué tan cerca estamos de la expresión que queremos obtener. En este
caso, queremos ver que
1 2(k + 1)
uk+1 = .
(k + 1) + 1 (k + 1)
Prueba: Usaremos la definición recursiva de la sucesión para el término k + 1, lo que hará
emerger el término k, momento en el que podremos usar la hipótesis inductiva.
2(k + 1) − 1
uk+1 = 2 uk
(k + 1) + 1
Primero opero un poco en el interior de la fracción:
2k + 2 − 1
=2 uk
k+2
2k + 1
=2 uk
k+2
Ahora reemplazo uk por lo que vale según la hipótesis inductiva que establecimos:
2k + 1 1 2k
=2
k+2 k+1 k
Escribo el número combinatorio en términos de factoriales:
2k + 1 1 (2k)!
=2
k + 2 k + 1 k!(2k − k)!
2k + 1 1 (2k)!
=2 .
k + 2 k + 1 k!k!
¿A dónde quiero llegar?
Queremos obtener la tesis inductiva (escrita en rojo), es decir que
1 2(k + 1)
uk+1 = .
(k + 1) + 1 (k + 1)
Pero si calculamos esta expresión un poco más obtenemos lo siguiente:
1 2k + 2
uk+1 = .
k+2 k+1
Y si ahora desarrollamos el número combinatorio obtenemos lo siguiente:
1 (2k + 2)! 1 (2k + 2)!
uk+1 = = .
k + 2 (k + 1)!(2k + 2 − (k + 1))! k + 2 k + 1)!(k + 1)!
Hemos de comparar qué tan cerca estamos desde
2k + 1 1 (2k)!
2
k + 2 k + 1 k!k!
para llegar a
1 (2k + 2)!
.
k + 2 (k + 1)!(k + 1)!
Y, a partir de las similitudes y diferencias, tenemos que trabajar la expresión verde para llegar
a la roja, momento en el cual habrá terminado la prueba.
Siguiendo con la prueba
Siguiendo con lo que habíamos obtenido antes de detenernos a ver qué nos faltaba, llegamos
a
2k + 1 1 (2k)!
uk+1 = 2
k + 2 k + 1 k!k!
1 (2k)!
= 2(2k + 1)
k+2 (k + 1)k!k!
1 (2k)!
= 2(2k + 1) .
k+2 (k + 1)!k!
Cálculos auxiliares
Si volvemos a contrastar lo que tenemos con aquello a lo que queremos llegar, observaremos
que en el numerador de la última fracción tenemos (2k)! y que nos gustaría hacer aparecer allí
(2k + 2)!. Conviene, en tal caso, tratar de hallar una relación entre estos dos factores.
(2k + 2)!
(2k + 2)! = (2k + 2)(2k + 1)(2k)! ⇒ (2k)! = .
(2k + 2)(2k + 1)
Esto nos permite reemplazar (2k)! en la expresión que teníamos antes. Volvamos a la prueba.
Volviendo a la prueba
Habíamos quedado En
1 (2k)!
uk+1 = 2(2k + 1)
k+2 (k + 1)!k!
1 1
= 2(2k + 1) (2k)!
k+2 (k + 1)!k!
1 1 (2k + 2)!
= 2(2k + 1)
k+2 (k + 1)!k! (2k + 2)(2k + 1)
1 2(2k + 1)(2k + 2)!
=
k + 2 (2k + 2)(2k + 1)(k + 1)!k!
1 2(2k + 2)!
beginalign∗ =
k + 2 (2k + 2)(k + 1)!k!
1 2(2k + 2)!
beginalign∗ =
k + 2 2(k + 1)(k + 1)!k!
1 (2k + 2)!
beginalign∗ =
k + 2 (k + 1)!(k + 1)k!
1 (2k + 2)!
beginalign∗ =
k + 2 (k + 1)!(k + 1)!
1 (2(k + 1))!
beginalign∗ =
(k + 1) + 1 (k + 1)!(2(k + 1) − (k + 1))!
1 2(k + 1)
= .
(k + 1) + 1 (k + 1
si asumimos que uk = f (k) para algún k ∈ N se obtiene que uk+1 = f (k + 1). Por lo tanto,
probamos que un = f (n) para todos los naturales. □