Una sucesión de un conjunto $S$ es una aplicación de la forma:

$$ \begin{align*} \N &\longrightarrow S \newline 0 &\longmapsto S_0 \newline 1 &\longmapsto S_1 \newline \vdots \end{align*} $$

Una función recursiva de una sucesión específica cumple

• Uno o más términos iniciales

• Relación de recurrencia: una regla para determinar términos siguientes a partir de los anteriores.

  Es una ecuación o fórmula que expresa $a_n$ con un subconjunto de $\Set{a_0, a_1, \ldots, a_{n-1}}$.

El término general o solución de la sucesión es la expresión que permite calcular cualquier término, sin depender de los anteriores.

Resolver una relación de recurrencia consiste en encontrar las soluciones, dando una fórmula para calcular el término n-ésimo.

Se llama Relación de Recurrencia Lineal Homogénea con Coeficientes Constantes (RRLHCC) a una expresión de la siguiente forma:

$$ a_n = c_1 a_{n-1} \; + \; \ldots \; + \; c_k a_{n-k} $$

Donde $c_i$ son constantes y $c_k \ne 0$.

$$ \begin{align*} a_n &= c_1 a_{n-1} \; + \; \ldots \; + \; c_k a_{n-k} \newline r^n &= c_1 r^{n-1} \; + \; \ldots \; + \; c_k r^{n-k} \newline r^n r^{k-n} &= c_1 r^{n-1} r^{k-n} \; + \; \ldots \; + \; c_k r^{n-k} r^{k-n}\newline r^k &= c_1 r^{k-1} \; + \; \ldots \; + \; c_{k-1} r \; + \; c_k = 0 \newline \end{align*} $$

La ecuación característica de una RRLHCC de orden $k$, es decir, que tiene $k$ condiciones iniciales, es de la forma:

$$ r^k = c_1 r^{k-1} \; + \; \ldots \; + \; c_{k-1} r \; + \; c_k = 0 $$

Sea $ a_n = c_1 a_{n-1} \; + \; \ldots \; + \; c_k a_{n-k} $ la RRLHCC de orden $k$ y las raices distintas y reales de la sucesión característica $r_1, \; \ldots, \; r_k$.

$$ a_n = \alpha_1 r_1^n \; + \; \ldots \; + \; \alpha_k r_k^n $$

Con las condiciones iniciales, obtenemos un sistema y calculamos $\alpha_1, \; \ldots, \; \alpha_k$.

Dada la relación de recurrencia, y suponemos que las raíces reales de la ecuación característica son $r_1, \; \ldots, \; r_s$ de multiplicidades (veces que se repiten) $m_1, \; \ldots, \; m_s$ respectivamente.

$$ \begin{align*} a_n = &(\alpha_{1 \; 0} \;+\; \alpha_{1 \; 1}n \;+\; \alpha_{1 \; 2}n^2 \;+\; \ldots \;+\; \alpha_{1 \; m_1 - 1} n^{m_1 - 1}) r_1^n \newline &(\alpha_{2 \; 0} \;+\; \alpha_{2 \; 1}n \;+\; \alpha_{2 \; 2}n^2 \;+\; \ldots \;+\; \alpha_{2 \; m_2 - 1} n^{m_2 - 1}) r_2^n \newline &\ldots \; + \newline &(\alpha_{s \; 0} \;+\; \alpha_{s \; 1}n \;+\; \alpha_{s \; 2}n^2 \;+\; \ldots \;+\; \alpha_{s \; m_s - 1} n^{m_s - 1}) r_s^n \newline = &\sum_{i=0}^{s} \left( \sum_{j=0}^{m_s - 1} \alpha_{i \; j} n^j \right) r_i^n \end{align*} $$

Se llama Relación de Recurrencia Lineal no Homogénea con Coeficientes Constantes (RRLHCC) a una expresión de la siguiente forma:

$$ a_n = \overbrace{c_1 a_{n-1} \;+\; \ldots \;+\; c_k a_{n-k}}^{\text{Parte homegénea}} \;+\; \overbrace{L(n)}^{\text{Parte no homogénea}} $$

Sea $a_n = c_1 a_{n-1} \;+\; \ldots \;+\; c_k a_{n-k} \;+\; L(n)$.

Si $a_n^{(p)}$ es una solución particular de la RR y si $a_n^{(h)}$ es una solución a la parte homogénea, entonces la solución es $$ a_n = a_n^{(p)} \;+\; a_n^{(h)}.$$

Dada una RRLnHCC $a_n = c_1 a_{n-1} \;+\; \ldots \;+\; c_k a_{n-k} \;+\; L(n)$ de forma que $L(n) = (p_0 \;+\; p_1 n \;+\; \ldots \;+\; p_t n^t) S^n = p_t(n)S^n$.

1. Si $S$ no es raíz de la RRLHCC asociada, entonces, tiene como solución particular $$ a_n^{(p)} = (\beta_0 \;+\; \beta_1 n \;+\; \ldots \;+\; \beta_t n^t) S^n.$$

2. Si $S$ es raíz de la RRLHCC asociada, entonces tiene como solución particular $$ a_n^{(p)} = (\beta_0 \;+\; \beta_1 n \;+\; \ldots \;+\; \beta_t n^t) S^n n^m$$ siendo $m$ la multiplicidad de la raíz.