Sucesiones y recurrencias
Qué es una sucesión
Una sucesión asigna a cada número natural un término: a uno, a dos, y así. Es una función cuyo dominio son los enteros. Se puede definir por su término general o por una regla de generación.
Término general
- Da el valor del término n directamente, sin pasar por los anteriores.
- Ejemplo simple: dos n más uno genera los impares desde tres.
- Es la forma más cómoda para calcular términos lejanos.
Relación de recurrencia
Una recurrencia define cada término en función de términos previos, más unos valores iniciales que arrancan la cadena. Sin los iniciales, la regla no tiene de dónde partir y nada queda determinado.
El ejemplo de Fibonacci
- Cada término es la suma de los dos anteriores.
- Arranca con dos valores semilla, cero y uno.
- Sus semillas son imprescindibles: la regla sola no fija la sucesión.
Resolver una recurrencia
Consiste en encontrar un término general equivalente que no obligue a calcular todos los previos. Es el salto de «paso a paso» a «salto directo», y a menudo revela el patrón de crecimiento.
Crecimiento y orden
- Lineal, cuadrático, exponencial: la forma de la recurrencia manda.
- Una duplicación en cada paso produce crecimiento exponencial.
- El orden de crecimiento decide si un cálculo es factible.
Inducción para demostrar
La inducción prueba que una propiedad vale para toda la sucesión: se verifica para el caso base y se demuestra que, si vale para uno, vale para el siguiente. Es el gemelo lógico de la recurrencia.
Recurrencia y recursión
- Un programa recursivo es una recurrencia hecha código.
- El caso base de la recursión son las semillas de la recurrencia.
- Sin caso base, la recursión no termina: el equivalente de no dar iniciales.
Coste de la recursión ingenua
Calcular cada término recomputando los anteriores puede explotar. La memoización guarda resultados ya calculados, igual que encontrar el término general evita repetir trabajo.
Sucesiones en datos
- Series temporales como sucesiones indexadas por el tiempo.
- Crecimientos compuestos siguen recurrencias lineales.
- Analizar tendencias es mirar el orden de crecimiento de la sucesión.
Errores frecuentes
- Dar la regla de recurrencia sin indicar los valores semilla.
- Confundir el término general con la recurrencia, que son descripciones distintas.
- Ignorar el coste de una recursión que recomputa los mismos términos.
Ejemplo resuelto: los primeros términos
Sea la recurrencia en que cada término es el doble del anterior más uno, arrancando en uno. Calcula los cuatro primeros términos.
- Fija la semilla: el primer término vale uno.
- Aplica la regla al segundo: dos por uno más uno igual a tres.
- Tercer término: dos por tres más uno igual a siete.
- Cuarto término: dos por siete más uno igual a quince.
- Observa el patrón: crece de forma casi exponencial.
¿Para qué sirve en la realidad?
Las recurrencias modelan el coste de algoritmos recursivos y el crecimiento de fenómenos compuestos: resolverlas permite predecir si un programa tardará segundos o siglos según el tamaño de la entrada.
Una recurrencia, para determinar por completo una sucesión, necesita además:
Toda sucesión admite tanto un término general como una descripción por recurrencia.
Sucesiones
Ordena los pasos para estudiar una sucesión dada por recurrencia:
Semilla
Regla
Términos
Cerrada
Relación de recurrencia
Definición de términos de una sucesión a partir de anteriores.
Une cada noción de sucesiones con su definición:
Paso a paso frente a salto directo
# Sucesiones y recurrencias ## Descripción ### término general ### recurrencia con semillas ## Comportamiento ### orden de crecimiento ### lineal o exponencial ## Prueba ### inducción ### caso base más paso
Inducción matemática
Demostrar propiedades de sucesiones paso a paso desde el caso base.
Escribe con palabras la recurrencia del interés compuesto (capital del año siguiente en función del actual) e indica cuál es la semilla y por qué sin ella no hay sucesión.