Fórmula recurrente

Una fórmula recurrente es una fórmula de la forma que expresa cada miembro de la secuencia en términos de los miembros anteriores y el número del miembro de la secuencia . $a_{n}=f(n,a_{n-1},a_{n-2},\dots,a_{np})$ $un$ $pags$ $norte$

La problemática general de los cálculos usando fórmulas recursivas es el tema de la teoría de funciones recursivas .

Una ecuación recurrente es una ecuación que conecta varios miembros consecutivos de una cierta secuencia numérica. Una sucesión que satisface tal ecuación se llama sucesión recurrente .

Ejemplos

La función factorial de un número natural satisface la fórmula recurrente: $n!={\begin{casos}1,&n=0;\\(n-1)!\cdot n,&n\geqslant 1.\end{casos))$

Los números de Fibonacci están dados por la fórmula recurrente lineal : $F_{n}={\begin{casos}0,&n=0;\\1,&n=1;\\F_{n-1}+F_{n-2},&n\geqslant 2.\ fin {casos}}$

El valor de la integral satisface la fórmula recurrente: $\textstyle I_{n}=\int \sin^{n}x\,dx$ $I_{n}={\frac {-\cos x\cdot \sin ^{n-1}x}{n}}+{\frac {n-1}{n}}I_{n-2 }.$

La solución a la ecuación diferencial de Bessel se puede escribir como una serie de potencias : $y''+(1/x)y'+(1-\nu ^{2}/x^{2})y=0$ $y=\sum \limits _{n=0}^{\infty}a_{n}x^{2n+\nu}.$

Para determinar los coeficientes , basta establecer que para todos . Después de eso, se obtiene inmediatamente el conocido resultado:

un

4n(n+\nu )a_{n}+a_{n-2}=0

n\geq 1

a_{n}={\frac {(-1)^{n}a_{0}}{2^{2^{n}}n!(1+\nu )(2+\nu )\ cpuntos (n+\nu)}}.

Longitud del lado al duplicar el número de lados de un n - gon regular inscrito : $a_{2n}={\sqrt {2R^{2}-2R{\sqrt {R^{2}-{\frac {a_{n}^{2}}{4}}}}}} ,\qquad n\geq 2,$

donde es el radio del círculo circunscrito .

R

Ecuaciones lineales recurrentes

Una ecuación lineal recurrente con coeficientes constantes tiene la forma:

f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots +a_{r}f_{n}=\varphi (norte).

Aquí hay números enteros no negativos, es una secuencia de números, son números constantes, , es una función dada de . $norte$ $f_{{n}}$ ${\displaystyle a_{1},a_{2},\ldots,a_{r))$ $a_{{r}}\neq 0$ $\varfi (n)$ $norte$

Ecuaciones recurrentes lineales homogéneas

Supongamos que una secuencia de números satisface una ecuación recurrente lineal homogénea , donde son números enteros no negativos, se dan números constantes y . $f_{0},f_{1},\puntos$ $f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots +a_{r}f_{n}=0$ $norte$ ${\displaystyle a_{1},\ldots,a_{r))$ $a_{{r}}\neq 0$

Denote por la función generadora de la secuencia . Construyamos un polinomio . Este polinomio puede verse como una función generadora de secuencias . Considere el producto de funciones generatrices . El coeficiente en y está determinado por la relación y es igual a cero. Esto significa que el polinomio tiene grado como máximo , por lo que el grado del numerador de la función racional es menor que el grado del denominador. $F(z)$ $f_{0},f_{1},\puntos$ ${\displaystyle K(z)=1+a_{1}z+a_{2}z^{2}+\ldots +a_{r}z^{r))$ $1,a_{1},a_{2},\ldots,a_{r},0,0,\dots$ $C(z)=F(z)K(z)$ $c_{{n+r}}$ $z^{{n+r}}$ ${\ estilo de visualización n \ geq 0}$ $c_{n+r}=f_{0}0+\ldots +f_{n-1}0+f_{n}a_{r}+\ldots +f_{n+r}1=f_{n +r}+a_{1}f_{n+r-1}+\ldots +a_{r}f_{n}$ $C(z)$ $r-1$ $F(z)={\frac {C(z)}{K(z)}}$

El polinomio característico de una ecuación lineal recurrente se llama polinomio . Las raíces de este polinomio se llaman características. El polinomio característico se puede representar como , donde son diferentes raíces características, son multiplicidades de raíces características, . ${\displaystyle g(z)=z^{r}+a_{1}z^{r-1}+\ldots +a_{r))$ $g(z)=(z-\alpha _{1})^{e_{1}}(z-\alpha _{2})^{e_{2}}\cdots (z-\alpha _ {s})^{e_{s}}$ ${\ estilo de visualización \ alfa _ {1}, \ ldots, \ alfa _ {s}}$ ${\displaystyle e_{1},\ldots,e_{s))$ $e_{1}+e_{2}+\ldots +e_{s}=r$

El polinomio característico y el polinomio están relacionados por la relación . De este modo, $g(z)$ $K(z)$ $K(z)=z^{r}g\left({\frac {1}{z}}\right)$

K(z)=(1-\alpha _{1}z)^{e_{1}}(1-\alpha _{2}z)^{e_{2}}\cdots (1-\ alfa _{s} z)^{e_{s}}.

Una función racional se puede representar como una suma de fracciones:

F(z)={\frac {C(z)}{K(z)}}=\sum_{i=1}^{s}\sum_{k=1}^{e_{i }}{\frac {\beta _{ik}}{(1-\alpha _{i}z)^{k}}}.

Cada fracción en esta expresión tiene la forma , por lo que se puede expandir en una serie de potencias de la siguiente forma $\beta (1-\alfa z)^{{-k}}$

\beta (1-\alpha z)^{-k}=\beta \left[1+(-k)(-\alpha z)+\ldots +{\frac {(-k)\cdots ( -k-n+1)}{n!}}(-\alpha z)^{n}+\ldots\right]

El coeficiente de en esta serie es igual a $z^{n}$

{\frac {\beta (n+k-1)\cdots k}{n!)}}\alpha ^{n}=\beta {\binom {n+k-1}{n}}\ alfa ^{n}=\beta {\binom {n+k-1}{k-1}}\alfa ^{n}.

Por lo tanto, la función generadora y es la solución general de la ecuación recurrente lineal, donde es un polinomio de grado como máximo . $F(z)=\sum_{n=0}^{\infty}\left(\sum_{i=1}^{s}p_{i}(n)\alpha_{i}^ {n}\derecho)z^{n}$ $f_{{n}}=\sum_{{i=1}}^{{s}}p_{{i}}(n)\alpha_{{i}}^{{n}}$ $alfiler)$ $norte$ $e_{{i}}-1$

Ejemplo

Sea necesario encontrar una solución a la ecuación con condiciones de contorno y . $f_{{n+2}}-f_{{n+1}}+f_{{n}}=0$ $f_{{0}}=1$ $f_{{1}}=1$

Esta ecuación tiene un polinomio característico , donde , . La solución general tiene la forma . Sustituyendo , obtenemos , . Obtenemos valores , . Por lo tanto $z^{2}-z+1=(z-\alpha _{1})(z-\alpha _{2})$ $\alpha _{{1}}={\frac {1}{2}}+i{\frac {{\sqrt {3}}}{2}}=e^{{i{\frac {\pi } {3}}}}$ $\alpha _{{2}}={\frac {1}{2}}-i{\frac {{\sqrt {3}}}{2}}=e^{{-i{\frac {\pi {3}}}}$ $f_{{n}}=c_{{1}}\alpha _{{1}}^{{n}}+c_{{2}}\alpha _{{2}}^{{n}}=c_ {{1}}e^{{{\frac {i\pi n}{3}}}}+c_{{2}}e^{({\frac {-i\pi n}{3}}} }$ $n=0,1$ $c_{{1}}+c_{{2}}=1$ $c_{{1}}\alfa_{{1}}+c_{{2}}\alfa_{{2}}=1$ $c_{{1}}={\frac {1}{2}}-i{\frac {1}{2{\sqrt {3}}}}$ $c_{{2}}={\frac {1}{2}}+i{\frac {1}{2{\sqrt {3}}}}$ $f_{n}=\left({\frac {1}{2}}-i{\frac {1}{2{\sqrt {3}}}}\right)\left(\cos \left ({\frac {\pi n}{3}}\right)+i\sin \left({\frac {\pi n}{3}}\right)\right)+\left({\frac {1 {2}}+i{\frac {1}{2{\sqrt {3}}}}\right)\left(\cos \left({\frac {\pi n}{3}}\right) -i\sin \left({\frac {\pi n}{3}}\right)\right)=\cos \left({\frac {\pi n}{3}}\right)+{\frac {1}{\sqrt {3}}}\sin \left({\frac {\pi n}{3}}\right)$

Aplicaciones

Existe una fórmula que expresa el término general de una sucesión lineal recurrente en función de las raíces de su polinomio característico. Por ejemplo, para la sucesión de Fibonacci, dicha fórmula es la fórmula de Binet . Las fórmulas recursivas se utilizan para describir el tiempo de ejecución de un algoritmo que recursivamente se llama a sí mismo. En tal fórmula, el tiempo requerido para resolver el problema con el volumen de entrada se expresa en términos del tiempo para resolver las subtareas auxiliares. [una] $norte$

Véase también

Secuencia recurrente lineal
función recursiva
recursión
Teorema principal de las relaciones recursivas (una solución simplificada de algunos tipos de relaciones recursivas que surgen en el análisis de la complejidad de los algoritmos recursivos)

Notas

↑ T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmos. Construcción y análisis = Introducción a los Algoritmos / I. Krasikov. - Editorial "Williams", 2005. - S. 79. - 1296 p.

Literatura

Fujisawa T., Kasami T. Matemáticas para ingenieros de radio: teoría de estructuras discretas. - M. , editorial = Radio y comunicación, 1984. - 240 p.