Digamos que estás en una fiesta con otras nueve personas y todos se dan la mano exactamente una vez. ¿Cuántos apretones de manos se producen?

Este es el "problema del apretón de manos" y es uno de mis favoritos. Como profesora de matemáticas, me encanta porque hay muchas formas diferentes de llegar a la solución, y la diversidad e interconexión de esas estrategias ilustran maravillosamente el poder del pensamiento creativo en matemáticas.

Una solución es la siguiente: comience con cada persona estrechando la mano de los demás. Diez personas, con nueve apretones de manos cada una, producen 9 × 10 = 90 apretones de manos en total. Pero esto cuenta cada apretón de manos dos veces (una vez desde la perspectiva de cada agitador), por lo que el número real de apretones de manos es $latex frac{90}{2} = 45$. ¡Un argumento de conteo simple y encantador para ganar!

También existe una forma completamente diferente de resolver el problema. Imagina que los invitados llegan uno a la vez, y al llegar, dan la mano a todos los presentes. La primera persona no tiene manos para estrechar, por lo que en un grupo de una sola persona no hay apretones de manos en total. Ahora llega la segunda persona y le da la mano a la primera. Esto agrega un apretón de manos al total, por lo que en un grupo de dos personas, hay 0 + 1 = 1 apretones de manos en total. Cuando llega la tercera persona y da la mano a los dos primeros invitados, esto suma dos apretones de manos al total. La llegada de la cuarta persona añade tres apretones de manos al total, y así sucesivamente.

Esta estrategia modela la secuencia de apretones de manos de forma recursiva, lo que significa que cada término de la secuencia se define en relación con los que le preceden. Probablemente estés familiarizado con la secuencia de Fibonacci, la secuencia recursiva más famosa de todas. Comienza con 1, 1, 2, 3, 5, 8, 13, 21 y continúa con cada término posterior igual a la suma de los dos anteriores.

Como veremos a continuación, la recursividad es un marco flexible y poderoso para pensar en una amplia gama de ideas matemáticas. Y aunque a los antiguos eruditos indios como Hemachandra se les atribuye el conocimiento de este tipo de secuencias desde 1150, todavía ofrecen desafíos intrigantes para los matemáticos de hoy.

Veamos cómo el pensamiento recursivo ayuda con el problema del apretón de manos. Si hacemos que $latex a_n$ sea igual al número de apretones de manos en un n-persona parte, podemos representar esta relación recursiva con la siguiente fórmula:

$látex a_n = a_{n-1} + n–1$

Esto nos dice que el número de apretones de manos en un n-persona fiesta ($latex a_n$) es igual al número de apretones de manos en un (n − Fiesta de 1) persona ($latex a_{n-1}$) más n − 1 apretón de manos más, capturando la idea de que cuando llega una nueva persona añade un número determinado de nuevos apretones de manos a los que ya se han producido.

En nuestra versión particular del problema del apretón de manos, queremos saber $latex a_{10}$, el número de apretones de manos en una fiesta de 10 personas, para encontrar que usamos la relación recursiva

$látex a_{10} = a_9 + 9$

Para encontrar el valor de $latex a_{10}$, solo necesitamos saber el valor de $latex a_9$ y sumarle 9. ¿Cómo encontramos el valor de $latex a_9$? ¡Usando recursividad, por supuesto!

$látex a_9 = a_8 + 8$

Ahora, para encontrar el valor de $latex a_8$, necesitamos encontrar el valor de $latex a_7$, lo que requiere conocer $latex a_6$, y así sucesivamente. En este punto, es posible que le preocupe que esto continúe para siempre en una especie de descenso infinito, pero una vez que llegamos a $latex a_1$ terminamos, porque sabemos que no hay apretones de manos en total en una fiesta de una sola persona.

$látex a_1 = 0$

Este valor inicial o "semilla" es una característica clave de una secuencia recursiva. Garantiza que este proceso de retroceder a través de la secuencia utilizando la relación recursiva finalizará. Una vez que alcanza el valor inicial, el retroceso se detiene y luego puede avanzar a través de la lista para obtener el valor que desea.

$látex a_1 = 0$

$látex a_2 = a_1 + 1 = 0 + 1 = 1$

$látex a_3 = a_2 + 2 = 1 + 2 = 3$

$látex a_4 = a_3 + 3 = 3 + 3 = 6$

$cdots de látex$

$látex a_{10} = a_9 + 9 = 36 + 9 = 45$

Al revisar la lista, vemos que hay 45 apretones de manos en total en una fiesta de 10 personas, lo que concuerda con nuestro cálculo inicial. Si se parece en algo a mis alumnos, podría preguntarse por qué necesitamos otra forma de resolver este problema cuando ya sabemos la respuesta, especialmente porque este segundo enfoque parece llevar más tiempo.

Es una buena pregunta. Una respuesta es que el enfoque recursivo nos da una visión completamente diferente de lo que sucede en este problema, y ​​perspectivas diferentes son útiles en matemáticas, como lo son en todas las cosas. Nos brindan diferentes oportunidades para comprender conceptos y nos permiten utilizar diferentes herramientas, que pueden ayudarnos cuando estamos estancados.

En particular, la recursividad es útil porque está presente en todas partes en matemáticas. Surge, por ejemplo, en las relaciones lineales que todo el mundo aprende en la clase de matemáticas, aquellas que se caracterizan por una tasa de cambio constante y se representan mediante líneas en el plano. Una función lineal como $latex f(x) = 3x + 5$ puede considerarse como una fórmula recursiva:

$látex a_0 = 5$

$látex a_n = a_{n-1} + 3$

Aunque la forma más obvia de pensar en $látex f(2)$ puede ser que $látex f(2) = 3 veces 2 + 5 = 11$, otra forma es que $látex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Modelar recursivamente la característica fundamental de las funciones lineales (la tasa de cambio constante) nos brinda otra forma de pensar en esta relación. Lo mismo se puede hacer con funciones exponenciales caracterizadas por un cambio multiplicativo constante.

El pensamiento recursivo también funciona más allá de las secuencias de números. Si alguna vez resolvió un sistema de ecuaciones, probablemente haya aplicado un enfoque recursivo. para resolver el sistema

$látex 2x + y = 10$

$látex 3x – y = 5$

Primero puedes sumar las dos ecuaciones para eliminar la y variable, lo que da como resultado la ecuación $látex 5x = 15$. Resuelve esto para obtener $latex x =$ 3, sustituye para encontrar $latex y = 4$ y listo. Este enfoque utiliza un algoritmo recursivo, donde la solución a un sistema se construye a partir de la solución a sistemas más pequeños y relacionados. Por ejemplo, para resolver un sistema 3 × 3, eliminas una variable para convertirlo en un sistema 2 × 2 y luego otra vez para convertirlo en un sistema 1 × 1. Esta única ecuación fácil de resolver es como el valor inicial de este proceso recursivo. Señala el final del retroceso y desde allí se avanza hacia atrás en la cadena de ecuaciones, como en una secuencia recursiva.

Incluso existen técnicas de prueba recursivas. Por ejemplo, una fórmula famosa en geometría es la fórmula de la suma de los ángulos del polígono, que dice que la suma de las medidas de los ángulos interiores de un nEl polígono de lados es $látex (n-2) multiplicado por 180^{circ}$. Una forma de probar este resultado es comenzar con una n-Continúa e imagina qué pasaría si quitaras un triángulo.

Quitar un triángulo convierte el n-gon en un (n − 1)-gon, y también elimina 180 grados de la medida del ángulo interior. Esta es una relación recursiva: la suma de los ángulos interiores de un n-gon es 180 grados más que la suma de los ángulos interiores de un (n − 1)-gón. Para establecer el resultado general, siga eliminando triángulos hasta alcanzar el valor inicial, lo que en esta situación ocurre cuando ha eliminado todos menos tres de los n-vértices de gon. En este punto, el polígono inicial se ha reducido a un triángulo, cuya suma de ángulos interiores se sabe que es 180 grados. Ahora regrese hacia arriba, agregando 180 grados en cada paso, y obtendrá la fórmula.

Volviendo a nuestro grupo, el problema del apretón de manos en sí nos muestra lo que es posible cuando pensamos creativamente y luego conectamos esas múltiples perspectivas diferentes de un problema. Si jugamos con el modelo recursivo para nuestra secuencia de apretones de manos:

$látex a_1 = 0$

$látex a_n = a_{n-1} + n – 1$

surge un bonito patrón:

$látex a_2 = a_1 + 1 = 0 + 1$

$látex a_3 = a_2 + 2 = 0 + 1 + 2$

$látex a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$cdots de látex$

$látex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

Ahora tenemos una forma nueva y general de pensar en el problema: el número de apretones de manos en un n-persona parte es igual a la suma de la primera n − 1 entero positivo.

Piense en nuestro enfoque original. en un n-Fiesta de personas, cada persona se dará la mano a la otra. n − 1 personas. El producto $latex n (n-1)$ cuenta cada apretón de manos dos veces, por lo que el número total de apretones de manos es $latex frac{n(n-1)}{2}$. Pero como nuestros diferentes métodos cuentan lo mismo, tienen que producir el mismo resultado. En particular, esto significa:

$látex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

Al conectar diferentes enfoques al problema del apretón de manos, obtenemos una fórmula cerrada para la suma de la primera n − 1 entero positivo. Pero obtenemos aún más: la expresión $latex frac{n(n-1)}{2}$ implica una fracción, pero como es igual a una suma de números enteros, también debe ser un número entero. Esto prueba un hecho simple de la teoría de números: por cada número entero n, $fracción de látex{n(n-1)}{2}$ es un número entero.

Este mismo tipo de argumento sigue impulsando las matemáticas modernas. Como ejemplo, los investigadores de principios de la década de 2000 demostró algunos resultados sorprendentes sobre secuencias recursivas conocidas como secuencias de Somos mostrando que ellas también cuentan algo. A través del poder de las conexiones creativas, los matemáticos descubrieron una vez más adónde podían ir al comprender dónde habían estado.

Ejercicios

1. Encuentre una fórmula cerrada para la secuencia que se define recursivamente como
$látex a_1 = 1$
$látex a_n = a_{n-1} + 2n – 1$

2. Al final de la columna, se demostró que la expresión $latex frac{n(n-1)}{2}$ es un número entero aunque la expresión involucra una fracción, porque $latex frac{n(n-1 )}{2}$ es el resultado de contar algo. También hay un argumento de la teoría de números que muestra que esta expresión debe ser un número entero. ¿Qué es?

3. Encuentra los primeros términos de la secuencia recursiva.
$látex a_1 = 1$
$látex a_n = frac{1}{1+a_{n-1}}$

4. Encuentra los primeros términos de la secuencia recursiva.
$látex a_1 = 1$
$látex a_2 = 1$
$látex a_n = a_{n-1} – a_{n-2}$