Introducción

En esta entrada revisaremos el concepto de recursión en un sentido matemático y revisaremos algunos ejemplos. Probablemente ya hayas escuchado el término, pues verás que es una herramienta útil para definir funciones en términos de las evaluaciones pasadas.

La suma de los primeros n números naturales

Carl Friedrich Gauss fue un matemático alemán del siglo XVIII el cual es uno de los más importantes en distintas disciplinas matemáticas como la teoría de números, la geometría y estadística. Sus aportes son varios en estas y más áreas por lo que nos tomaría varios años de estudio para llegar a muchos de sus resultados. En esta ocasión veremos uno de sus razonamientos más famosos el cual muchos le atribuyen cuando este solo estaba en el colegio cuando aún era niño.

Se dice que el profesor de su clase de matemáticas había castigado a todo el salón haciéndoles sumar los números naturales del $1$ al $100$. La historia dice que no pasó mucho tiempo (y mucho menos del esperado por el profesor) hasta que Gauss llegó con la respuesta «5050». El razonamiento que tuvo fue el siguiente: Para llegar a la suma, pondremos los números del $1$ al $100$ en una lista, y debajo los mismos números pero al revés, es decir, del $100$ al $1$, y notemos que sumando uno a uno los números de las dos listas como los hemos acomodado, queda un mismo número:

$$\begin{array}{cccccc}
&1 & 2 & \dots &99 & 100 \\
+&100 & 99 & \dots &2 & 1 \\
=&101 & 101 & \dots &101 & 101\\
\end{array}$$

De manera que si tenemos los primeros $100$ números, entonces el número resultante de la suma es $101$, de manera que si sumamos estos números, estaríamos sumando $100$ veces el número $101$, pero como hemos sumado dos veces la lista, entonces deberemos dividir entre $2$ para obtener la suma real. Dicho de otra forma: $$ \sum_{i=0}^{100} i = \frac{100(100+1)}{2} .$$
Si recuerdas, esta es la fórmula que probamos en la entrada pasada, pues en el caso general: $$ \sum_{i=0}^{n} i = \frac{n(n+1)}{2} $$.

Viendo la suma como recursión

Sigamos pensando en el ejemplo. Para cada $n \in \mathbb{N}$, llamemos $$S_n = \sum_{i=0}^{n} i = \frac{n(n+1)}{2} .$$ Y nota que para cada número natural $n$ se cumple que:

1. $S_0=0$
2. Si $n>0$ entonces $S_n = S_{n-1}+n$

Nota ahora que podemos definir a $S_n$ únicamente en términos de la suma de su antecesor con el número. Esto quiere decir que si nos pidieran calcular $S_{51},S_{52},S_{53}$, primero podemos calcular $S_{51}$ sumando todos los números del $0$ al $51$, pero una vez tengamos ese resultado, no es necesario volver a sumar todos los números para $S_{52}$, sino que basta saber quién es $S_{51}$ y sumarle $52$ para obtener el término deseado, lo mismo para el siguiente número de la sucesión $S_{53}=S_{52}+53$. A $S$ se le puede ver como una función $S:\mathbb{N} \rightarrow \mathbb{N} $ donde $S_n$ hace referencia a la función $S$ valuada en $n$, esto quiere decir que $S(n)=S_n$. A esta función se le llamará una función recursiva.

Definición. Una función $\phi: \mathbb{N} \rightarrow \mathbb{N} $ se dice tener la propiedad de recursión si existe $a \in \mathbb{N} $ y una función $f : \mathbb{N} \rightarrow \mathbb{N} $ tal que:

1. $\phi(0)=a$
2. Si $n>0$ entonces $\phi(\sigma(n)) = f(\phi(n))$

Veamos esta definición por partes. Retomemos nuestro ejemplo de la suma de los primeros números naturales. La función que es recursiva es $\phi$, esta función debe satisfacer dos condiciones. La primera condición es que se defina a dónde «manda» el $0$, es decir, hace falta saber cómo empezar la definición recursiva, en este caso, se trata de cómo definimos el comportamiento de la función en el primer número del conjunto de los números naturales. La segunda condición se pone más interesante, pues lo que nos dice es que existe una función $f$ tal que la función $\phi$ evaluada en el sucesor de $n$ ($\sigma(n)=n+1$) es la función $f$ valuada en $\phi (n)$. Lo que quiere decir esta oración es que «Si quieres saber quién es $\phi(n+1)$ y ya sabes quién es $\phi (n)$, entonces basta hacerle algo a ese resultado (valuar ese resultado en $f$) para obtener lo querido».

En nuestro ejemplo de la función $S$ (en la definición, esta sería la función $\phi$), la función $f$ es aquella que a cada suma parcial le agrega el número correspondiente. Esto quiere decir que $f$ es la función: $$\begin{align*} f(S(n)) &= S(n)+n \\&= S(n+1)=S(\sigma(n))\end{align*}.$$

Teorema de recursión débil

El siguiente teorema nos garantiza no solo la existencia de funciones recursivas, sino que además nos garantiza que esta es una herramienta para conjuntos distintos al de los números naturales:

Teorema (Recursión Débil): Sea $X$ un conjunto y $x_{0}\in X$. Supongamos que tenemos una función $f:X\to X$. Entonces existe una única función $\phi:\mathbb{N}\to X$ tal que:

• $\phi(0)=x_{0}$
• $\phi(\sigma(n))=f(\phi(n)).$

La demostración de este teorema se verá en el curso de Álgebra Superior II. Y a grandes rasgos nos garantiza el hecho de que las definiciones de las funciones por recursión son matemáticamente válidas. En otras palabras, muestra que somos capaces de definir y usar funciones recursivas.

Algunos ejemplos

Veamos otro ejemplo de este tipo de funciones. Sea $n \in \mathbb{N}$ Definamos $$ n! = n*(n-1)*(n-2)*\dots*2*1.$$ Por ejemplo, $3!=3*2*1=6$. Nota que esta es una función que podemos describir como recursiva al establecer las siguientes condiciones:

1. $0!=1$
2. $n!=(n-1)!*n.$

Como veremos en siguientes entradas, esta función llamada factorial se utilizará mucho en conteo y combinatoria, pues nos hablará de el número de formas de combinar un conjunto con algún número de elementos.

El siguiente ejemplo requiere de una pequeña definición:

Definición. Sea $a$ una función. La función $a$ es una sucesión si $a : \mathbb{N} \rightarrow \mathbb{N} $ es una función entre números naturales.

Esta definición nos indica que a las funciones entre números naturales también se les conoce como sucesiones, muchas veces este no será el nombre común al que se refieran a las funciones de $ \mathbb{N} $ en $ \mathbb{N} $ pero si en alguna ocasión ves el término, sabrás a qué se refiere. También es común, al estar hablando de sucesiones, de escribir las evaluaciones de $a$ en cada término $n$ simplemente como $a_n$ es decir $a_n=a(n)$.

Supongamos ahora que tenemos la sucesión definida como $$a_n=5n+2$$. Los cinco primeros términos de esta sucesión son:$$a_0=2$$ $$a_1=7$$ $$a_2=12$$ $$a_3=17$$ $$a_4=22$$ Notemos que podemos escribir esto de forma recursiva, para ello, notemos que únicamente en cada paso estamos sumando un 5, de manera que $$a_{n+1}=a_n+5.$$Adicionalmente, ya sabemos cuánto vale en el $0$, así la siguiente proposición demuestra este hecho:

Proposición $a_n$ puede definirse de forma recursiva como:

1. $a_0=2$
2. $a_{n+1}=a_n+5.$

Demostración (por inducción)

Base inductiva. Es claro que $$a_0 = 2 = 0*5+2$$ De manera que se cumple la base de inducción.

Hipótesis inductiva. Supongamos que para $n\geq 0$ se cumple que $$a_n = a_{n-1}+5=5n+2.$$

Paso inductivo. Para demostrar que $$a_{n+1}=a_n+5$$ como dice la proposición, notemos que por definición de la sucesión, $$a_{n+1}=5(n+1)+2=5n+2+5.$$
Ahora, por hipótesis de inducción, $$a_n=5n+2.$$De esta forma, $$a_{n+1}=5(n+1)+2)+5=a_n+5. $$ tal como se quería demostrar.

$\square$

Más adelante…

En esta entrada dimos la idea de lo que significa la recursión en las matemáticas, en la siguiente entrada usaremos esta idea para empezar a definir las operaciones básicas en los números naturales: la suma y el producto.

Tarea Moral

1. Muestra que hay una única función $\phi$ entre número naturales tal que:
   1. $\phi(0)=10$
   2. $\phi(\sigma(n))=2\phi(n)$
2. Da una definición explícita de la función del inciso anterior.
3. Da una definición recursiva para las siguientes sucesiones:
   • $a_n=2n$
   • $a_n=2n+1$
   • $a_n=2^n$
   • $a_n=0$

Entradas relacionadas

• Ir a Álgebra Superior I
• Entrada anterior del curso: Problemas de inducción
• Siguiente entrada del curso: Suma y producto de naturales y sus propiedades

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»