Sucesiones, recursividad y diferencias finitas

En este post voy a abordar de nuevo el tema de la recursividad a través de algunas sucesiones definidas de manera recursiva. Puesto que la recursión es un tipo de razonamiento muy útil en el problem solving de combinatoria, voy a plantear primero algunos ejemplos de modelación, un tema que se omite en la mayoría de los textos sobre el tema. Después de esos ejemplos, se aborda la sucesión aritmética y algunas sucesiones más generales definidas de manera recurrente, para finalmente concluir con algunos métodos para obtener el término n-ésimo de ciertas sucesiones recursivas. Uno de ellos es el de diferencias finitas. 

Algunos ejemplos de modelación recursiva

Permutaciones

¿De cuántas formas se pueden colocar n objetos distintos en una fila?

Solución: Sea $u_n$ el número de formas de colocar $n$ objetos en una fila. Mediante experimentación se pueden generar los casos iniciales: $a_1=1,a_2=2, a_3=6$,etc.

Para $n$ objetos se puede razonar así: pongo cualquiera de los $n$ al principio (n formas); los restantes $n-1$ se pueden colocar de $u_{n-1}$ formas --por hipótesis. De esta manera $u_n=nu_{n-1}$.

Escalera

¿De cuántas formas se puede subir una escalera de n escalones si está permitido subir en cada paso uno o dos escalones?

Solución: Si fuera de un solo escalón el número de formas es 1; si de 2, habría 2 formas. Si llamamos $u_n$ al número de formas de subir una escalera de n escalones de acuerdo a la regla antedicha, entonces tenemos que $u_1=1,u_2=2$.

Ahora supongamos que la escalera es de $n$ escalones. Las formas de subirla de acuerdo a la regla se clasifican en dos grandes grupos: el primer paso es de un escalón o el primer paso es de 2 escalones.

Si el primer paso es de 1 escalón, entonces nos quedan $n-1$ escalones por subir; y eso lo podemos hacer de $u_{n-1}$ formas. De la misma manera, si el primer paso es de dos escalones, entonces nos quedan por subir $n-2$ escalones; y eso lo podemos hacer de $u_{n-2}$ formas.

En resumen, el número de formas de subir una escalera de $n$ escalones siguiendo la regla es $u_n=u_{n-1}+u_{n-2}$ (para $n=3,4,5,\ldots$)

Sectores de un círculo definidos por n diámetros

En un círculo se trazan n diámetros. Determinar una recurrencia para el número de sectores formados.

Solución: Sea $u_n$ el número de sectores formados por n diámetros. Claramente $u_1=2,u_2=4$. Para obtener la recurrencia observemos que, al añadir un diámetro, dos de los sectores ya existentes se dividen en 2, añadiendo 2 sectores más a los ya existentes. De esta manera, la recurrencia es $u_n=u_{n-1}+2$

La progresión aritmética

Una sucesión $u_1, u_2, u_3,\ldots$, en la que cada término se obtiene del anterior sumándole una constante, se llama sucesión --o progresión-- aritmética. (Claramente debe ser dado un término inicial; de otra manera, no habría forma de construir o formar el segundo --y el proceso de formación de la sucesión no podría ni siquiera empezar.)

Consideremos como ejemplo la sucesión $1,3,5,7,\ldots$ de los números impares: iniciando con el 1, cada uno de los siguientes se forma sumando un 2 al anterior.

Formalmente, la sucesión de los impares se definiría así: $u_1=1, u_k=u_{k-1}+2$. A esta definición se le llama definición recursiva --por hacer depender cada término del anterior.

Supongamos ahora que deseamos saber cuál es el término n-ésimo, es decir, el término de la sucesión en la posición $n$ (por ejemplo, en la posición 2012).

Una forma de lograrlo es apoyándonos en la definición. Porque queremos $u_n$ --obviamente, en términos del término inicial y el incremento (1 y 2, respectivamente). Entonces, de acuerdo a la definición:

$$u_n=u_{n-1}+2=u_{n-2}+2+2=\ldots=u_{n-n+1}+2+2+\ldots+2$$

Un momento de reflexión debería conducirnos a la conclusión de que
$$u_n=1+2(n-1)$$
Es decir,
$$u_n=2n-1$$

En general, el término n-ésimo de una sucesión aritmética $a,a+d,a+2d,\ldots$ se puede obtener mediante el mismo procedimiento:
$$u_n=u_{n-1}+d=u_{n-2}+d+d=\ldots=u_{n-n+1}+d+d+\ldots+d$$

Y se hace evidente que, al llegar a $u_1=a$, mediante este procedimiento recursivo hacia atrás, el número de incrementos $d$ que se suman es $n-1$. Así que el término n-ésimo de una progresión aritmética con término inicial $a$ e incremento $d$ es
$$u_n=a+(n-1)d$$

Un poco más allá de la progresión aritmética

Supongamos ahora que tenemos una sucesión $u_k$ en la que cada término, a partir de uno inicial, se forma sumando no una constante sino un número $c_n$ que depende de la posición $n$ --en sí mismo $c_n$ forma otra sucesión que sigue un cierto patrón. 

Formalmente, consideremos la sucesión $u_n$ tal que:
$$u_1=a$$
$$u_n=u_{n-1}+c_n$$

(En lo que sigue voy a llamar a este tipo de sucesión progresión aritmética generalizada --aunque no sé si exista ese nombre...)

Apoyándonos en esta definición, el término n-ésimo se puede calcular así:

$$u_1=a$$

$$u_2=a+c_2$$

$$u_3=a+c_2+c_3$$

$$\vdots$$

$$u_n=a+c_2+c_3+ \ldots + c_n$$

Y, bueno, aquí nos encontramos con el problema de sumar los primeros $n-1$ términos de la sucesión $c_k$. Y ello solamente se puede hacer conociendo $c_n$, es decir, la naturaleza de la sucesión $c_n$.

Un ejemplo de sucesión aritmética generalizada son los números triangulares:
$$u_1=1$$
$$u_n=u_{n-1}+n$$

Según la fórmula recién obtenida, el término n-ésimo de los números triángulares estaría dada por:
$$u_n=1+2+3+\ldots+n$$

Es decir, el término n-ésimo de los números triángulares es la suma de los primeros n enteros positivos. (Una suma que sabemos es $n(n+1)/2$.

Métodos para obtener el término n-ésimo

Posiblemente la forma más fácil de resolver una ecuación de recurrencia sea mediante inducción matemática. Se generan los primeros términos y se conjetura el término general.

Un ejemplo: las torres de Hanoi (número mínimo de movidas). Es claro que si se tiene un solo disco (n=1), el mínimo de movidas es ($T_n=1$); si son dos discos ($n=2$), el mínimo de movidas es $T_n=3$. Cuesta un poco más de reflexión el ver que $T_3=7,T_4=15$.

Para formular la recurrencia es necesario razonar recursivamente: Si tengo 4 discos y ya sé que $T_3=7$, entonces se puede razonar así: paso los tres discos superiores al poste intermedio en 7 movidas ($T_3=7$), después paso el poste inferior a su destino (poste 3) en una movida, y finalmente paso los 3 discos en el intermedio al poste destino en 7 movidas. De manera que, con 4 discos, el mínimo de movidas es 7+1+7=15 movidas.

En general --y razonando de esta manera-- se tiene $T_n=2T_{n-1}+1$. Con esta fórmula recursiva se pueden generar más datos: $$T_5=31,T_6=63,T_7=127,\ldots$$
Así que se puede conjeturar que $T_n=2^n-1$.

Ahora inducción: $T_1=1$ (caso base) y $T_n=2^n+1$ (hipótesis de inducción).
Pero, $$T_{n+1}=2T_n+1$$

Por tanto, $$T_{n+1}=2T_n+1=2[2^n-1]+1=2^{n+1}-2+1=2^{n+1}-1$$

Diferencias finitas: su relación con derivadas

Como se sabe, el cociente diferencial de una función $f$ se define como
$$\frac{f(x+h)-f(x)}{h}$$
La derivada de $f$ se obtiene tomando el límite cuando $h$ (el incremento) tiende a cero. Es fácil demostrar, de acuerdo a la definición, que la derivada de una función constante es cero y la de una función lineal $f(x)=ax+b$ es $a$.

Un poco más difícil es demostrar que la de una función cuadrática $f(x)=ax^2+bx+c$ es $2ax+b$.

Bueno, la cosa es que las diferencias finitas son análogas a las derivadas, solamente que el incremento $h$ siempre es la unidad. Pero de cualquier manera, la analogía es útil para conjeturar la solución de una ecuación de recurrencias. 

Ilustremos con el ejemplo de los números triangulares: $u_1=1, u_k=u_{k-1}+n$.

Si ponemos la recurrencia $u_{k+1}=u_k+n$ como $u_{k+1}-u_k=n$, lo que tenemos es que el cociente diferencial es $n$ --como si tuvieramos $f(x+1)-f(x)=x$. Y ello nos conduce a conjeturar que la solución $u_n$ debe ser de forma cuadrática: $u_n=An^2+Bn+C$.

Pero como $u_1=1,u_2=3,u_3=6$, se puede plantear el sistema:
$$A+B+C=1$$
$$4A+2B+C=3$$
$$9A+3B+C=6$$

Restando la primera de la segunda y después la segunda de la tercera, se elimina la $C$:
$$3A+B=2$$
$$5A+B=3$$
Restando de nuevo se obtiene: $2A=1$ o $A=1/2$. De aquí que $B=2-3A=2-3(1/2)=1/2$ y $C=1-A-B=1-1/2-1/2=0$.

Así que la solución es $u_n=n^2/2+n/2=\frac{n(n+1)}{2}$ como se quería. (Bueno, si se quiere ser purista, falta demostrar esta fórmula por inducción matemática.)

Suma de los primeros términos de una sucesión

Dada una sucesión $u_n$, la suma de sus primeros $n$ términos se puede calcular definiendo la sucesión de sumas parciales $s_1=u_1,s_k=s_{k-1}+u_k$.

Por ejemplo, dada la sucesión aritmética $u_1=1,u_k=u_{k-1}+2$ (los números impares), la suma de sus primeros $n$ términos se puede calcualar definiendo la sucesión de sumas parciales $s_1=u_1, s_k=s_{k-1}+u_k$.

Como ya sabemos que el término n-ésimo de la sucesión de impares es $u_n=2n-1$, entonces la sucesión de sumas parciales de impares se concretiza a $s_1=1,s_{k+1}=s_k+2k+1$.

Con el método de conjetura recién visto, la diferencia finita de $s_k$ es $s_{k+1}-s_k=2k+1$. Y se puede conjeturar que su término n-ésimo es cuadrático. Es decir, se puede conjeturar que $s_n=An^2+Bn+C$. Y con los primeros 3 términos $1,4,9$ es suficiente para plantear el sistema de ecuaciones que determina $A,B,C$:
$$1=A+B+C$$
$$4=4A+2B´C$$
$$9=9A+3B+C$$

Restando la primera de la segunda y la segunda de la tercera se obtiene el sistema
$$3A+B=3$$
$$5A+B=5$$

Y éste se resuelve por el mismo método. Restando la primera de la segunda, se tiene que $2A=2$. Es decir, $A=1$. Finalmente, es fácil ver que $S=C=0$.

Así, la suma de los primeros $n$ números impares es $s_n=n^2$.

Algunos ejercicios

1. Calcular el término n-ésimo de la sucesión $u_1=1,u_{k+1}=u_k+k^2$ (la suma de los primeros n cuadrados perfectos) utilizando el método de conjetura a partir de la diferencia finita.

2. Calcular la suma de los primeros cubos perfectos $s_k=1^3+2^3+\ldots+k^3$

Los saluda
jmd

PD: Podría ser de alguna utilidad para el lector interesado en el tema estudiar y resolver los ejercicios del paper Recurrence relations, de Chris Tuffley

PD2: Hay que decir que no todas las sucesiones pueden resolverse con diferencias finitas.