A menudo es posible desarrollar relaciones entre los elementos de una sucesión. Tales relaciones se llaman relaciones de recurrencia. Se ilustrará el concepto con un ejemplo y luego, se dará una definición más formal.

Ejemplo:
Una persona invierte $1,000.00 pesos al 12% de interés compuesto anual. Si A_n representa el monto de cada n años, determinar una relación entre A_n y A_n-1.

Al cabo de n - 1 años el monto será A_n-1. Después de un año mas se tendrá la cantidad de A_n-1 más el interés del año, entones:

A_n = A_n-1 + (0.12)A_n-1

= 1.12A_n-1

El valor inicial A_o = 1000

que junto con la ecuación anterior permite calcular el valor de A_n n.

Por lo tanto al final del tercer año la cantidad es $1,404.93 pesos. Se puede efectuar para cualquier valor de n y se obtiene:

Al cabo de 20 años la cantidad resultante es: (1.12)²⁰ (1000) = $9,646.30

La ecuación A_n = (1.12)A_n-1 proporciona un ejemplo de una relación de recurrencia. Tal relación define una sucesión geométrica dando el n-ésimo valor en términos de algunos de los antecesores .Los valores dados explícitamente tales como A_o = 1000 se denominan condiciones internas.

Definición:
Una relación de recurrencia para una sucesión a_o, a₁, a₂, …, a_n es una ecuación que relaciona a_n con alguno de sus antecesores a_o, a₁, a₂, …, a_n-1.

Ejemplo:
Una de las más antiguas relaciones de recurrencia define la sucesión de Fibonacci. Esta sucesión se encuentra por primera vez en el libro de este autor, Liber Abaci (1202) donde él se preguntó lo siguiente: ¿cuántas parejas de conejos habrá después de un año, si al comienzo solo hay una pareja, y sabemos que cada pareja produce al mes una nueva pareja la cual se vuelve productiva al mes?. Se da por sentado que no ocurren muertes.

Sea f_i el número de parejas de conejos al cabo del i-ésimo mes. Entonces

f_o = 1 (i)

Al final de primer mes hay sólo una pareja ya que comienza a ser productiva después de un mes. Por consiguiente

f₁ = 1 (ii)

Las ecuaciones (i) y (ii) son las condiciones iniciales por la sucesión de Fibonacci. El aumento en las parejas de conejos f_n, f_n-1, del mes (n - 1) al mes (n) se debe a que cada pareja viva el mes (n - 2) produciendo una pareja adicional. Esto es:

f_n - f_n-1 = f_{n-2, ó bien}

f_n = f_n-1 + f_n-2 (iii)

La relación de recurrencia (iii) con las condiciones iniciales (i) y (ii) define una sucesión de Fibonacci.

Entonces despúes de un año la solución es f₁₂ = 233

Vamos a desarrollar los 12 primeros términos para comprobar la afirmación anterior.

NOTA: Una relación de recurrencia define generalmente una progresión.

Dicha relación de recurrencia no define una única progresión, a menos que se especifique los valores iniciales. Por ejemplo:

La relación de recurrencia a_n-1 = 3a, n 0, puede definir las siguientes progresiones geométricas:

i) 5, 15, 45, … ó
ii) 7, 21, 63, …

Pero si especificamos que en i) el valor inicial es a_o = 5, y en ii) que el valor inicial a_o = 7, entonces se define una progresión geométrica única en cada caso.

Ejemplo:
La sucesión 3⁰, 3¹, 3², ..., 3^r, donde el valor inicial 3⁰ = 1 con la relación de recurrencia a_r = 3a_r-1, dan como resultado la siguiente progresión:

1, 3, 9, 27, ..., 3^r-1, 3^r

Relaciones de Recurrencia Lineal con Coeficientes Constantes

Una relación de recurrencia de la forma:

C_oa_r + C₁a_r-1 + C₂a_r-2 + … + C_ka_r-k = f(r)        (i)

donde las C_i son constantes, se denomina recurrencia de recurrencia lineal con coeficientes constantes. La relacion de recurrencia (i) se conoce como una relación de recurrencia de k-ésimo orden siempre que tanto C_o y C_k sean distintos de cero.

Ejemplos:
a) 2a_r + 2a_r-1 = 2^r, es una relación de recurrencia lineal con coeficientes constantes de primer orden.

b) 3a_r - 5a_r-1 + 2a_r-2 = r² + 5, es una relación de recurrencia lineal con coeficientes constantes de segundo orden.

c) a_r + 7a_r-2 = 0, es una relación de recurrencia lineal con coeficientes constantes de segundo orden.

d) a_r = 3a_r-1 · a_r-2, no es una relación de recurrencia lineal con coeficientes constantes.

e) a_r = 3ra_r-1, no es una relación de recurrencia lineal con coeficientes constantes.

Si f(r) = 0, como ocurre en la relación de recurrencia c), se dice que la relación de recurrencia es lineal homogénea con coeficientes constanta.

Consideremos la relación de recurrencia 3a_r - 5a_r-1 + 2a_r-2 = r² + 5.

Supóngase que nos dan los valores iniciales a₃ = 3 y a₄ = 6, podemos calcular a a₅ y a₆ como sigue:

a₂ = 9
a₁ = 25
a_o = 107/2

En general una relación de recurrencia de k-ésimo orden con coeficientes constantes como en (ii), si k valores consecutivos de la función numérica de a a_m-k, a_m-r-1, …, a_m-1; son conocidos para algún m, los valores de a_m puede calcularse de acuerdo con (i) a saber:

a_m = -1/C_o[C₁a_m-1 + C₂a_m-2 + … + C_ka_m-k - f(m) ]