Recurrencias y aritmética · Definición

Relación de recurrencia

matemáticas discretasrecurrencias

Antes de empezar necesitas conocer

Muchos problemas de conteo se resuelven describiendo cómo un caso grande se construye a partir de casos más pequeños, y eso es exactamente una recurrencia.

Definición

Una relación de recurrencia es una ecuación que expresa cada término \(a_n\) de una sucesión en función de los \(k\) anteriores; con valores iniciales, determina toda la sucesión.

\[a_n=f(a_{n-1},a_{n-2},\dots,a_{n-k})\]

Una recurrencia tiene dos partes que deben ir juntas: la regla que calcula \(a_n\) a partir de términos previos y las condiciones iniciales que arrancan la sucesión. Sin condiciones iniciales hay infinitas sucesiones que cumplen la misma regla; con ellas, la sucesión queda determinada y puede calcularse paso a paso. La cantidad de valores iniciales necesarios es el orden \(k\) de la recurrencia, el número de términos anteriores que usa la regla.

Modelar un problema consiste en razonar sobre el último paso. En las torres de Hanói, para mover \(n\) discos hay que mover \(n-1\), pasar el mayor y volver a mover \(n-1\): \(T_n=2T_{n-1}+1\). Con \(n\) rectas en posición general, la recta nueva corta a las \(n-1\) anteriores y crea \(n\) regiones nuevas: \(R_n=R_{n-1}+n\). Las cadenas binarias sin dos ceros seguidos terminan en 1 o en 10, lo que da \(a_n=a_{n-1}+a_{n-2}\).

Calcular los primeros términos suele sugerir una fórmula cerrada, como \(T_n=2^n-1\) o \(R_n=1+n(n+1)/2\), que se confirma con inducción matemática: se verifica el caso base y se usa la recurrencia en el paso inductivo. Un error frecuente es olvidar que el índice de la regla puede empezar en \(n=1\) o \(n=2\) según el orden, y que los valores iniciales no se obtienen de la regla. Más adelante se verá un método sistemático para resolver las recurrencias lineales.

Para pensar

¿Cuántas sucesiones cumplen \(a_n=a_{n-1}+a_{n-2}\) sin fijar condiciones iniciales?

Infinitas: cada pareja de valores \((a_0,a_1)\) produce una sucesión distinta.

Demuestra por inducción que \(T_n=2^n-1\) cumple \(T_n=2T_{n-1}+1\) con \(T_0=0\).

Caso base: \(T_0=2^0-1=0\). Paso: si \(T_{n-1}=2^{n-1}-1\), entonces \(T_n=2(2^{n-1}-1)+1=2^n-1\).

Ejercicios 10

  1. Sea \(a_0=2\) y \(a_n=3a_{n-1}-1\) para \(n\ge1\). ¿Cuánto vale \(a_4\)?
  2. Sea \(a_0=a_1=1\) y \(a_n=a_{n-1}+a_{n-2}\). ¿Cuánto vale \(a_6\)?
  3. Sea \(a_0=1\) y \(a_n=a_{n-1}+2n\). ¿Cuánto vale \(a_5\)?
  4. Si \(a_0=3\) y \(a_n=2a_{n-1}\), ¿cuál es una fórmula para \(a_n\)?
  5. En las torres de Hanói, el mínimo de movimientos cumple \(T_n=2T_{n-1}+1\) con \(T_0=0\). ¿Cuánto vale \(T_6\)?
  6. ¿Cuántos valores iniciales hacen falta para determinar una sucesión con \(a_n=a_{n-1}+a_{n-2}\)?
  7. Sea \(a_n\) el número de cadenas binarias de longitud \(n\) sin dos ceros seguidos. Se cumple \(a_n=a_{n-1}+a_{n-2}\) con \(a_1=2\) y \(a_2=3\). ¿Cuánto vale \(a_5\)?
  8. La sucesión \(a_0=1,\ a_1=3\) y \(a_n=2a_{n-1}-a_{n-2}\), ¿qué fórmula cumple?
  9. Con \(n\) rectas en posición general, el número de regiones del plano cumple \(R_n=R_{n-1}+n\) y \(R_0=1\). ¿Cuánto vale \(R_6\)?
  10. Sea \(a_0=1\) y, para \(n\ge1\), \(a_n=a_0+a_1+\cdots+a_{n-1}\). ¿Cuánto vale \(a_6\)?

Referencias

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §8.1
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §5.6
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §10.1