En matemáticas , el algoritmo de Gosper , debido a Bill Gosper , es un procedimiento para encontrar sumas de términos hipergeométricos que son en sí mismos términos hipergeométricos. Es decir: supongamos que uno tiene a (1) + ... + a ( n ) = S ( n ) - S (0), donde S ( n ) es un término hipergeométrico (es decir, S ( n + 1) / S ( n ) es una función racional de n ); entonces necesariamente un ( n) es en sí mismo un término hipergeométrico, y dada la fórmula para un ( n ) algoritmo de Gosper encuentra eso para S ( n ).
Esquema del algoritmo
Paso 1: Encuentre un polinomio p tal que, escribiendo b ( n ) = a ( n ) / p ( n ), la razón b ( n ) / b ( n - 1) tiene la forma q ( n ) / r ( n ) donde q y r son polinomios y no q ( n ) tiene un factor de no trivial con r ( n + j ) para j = 0, 1, 2, .... (Esto siempre es posible, ya sea que la serie sea sumable en forma cerrada o no).
Paso 2: Encuentre un polinomio ƒ tal que S ( n ) = q ( n + 1) / p ( n ) ƒ ( n ) a ( n ). Si la serie es sumable en forma cerrada, entonces claramente existe una función racional f con esta propiedad; de hecho, siempre debe ser un polinomio y se puede encontrar un límite superior en su grado. La determinación de ƒ (o encontrar que no hay es tal ƒ ) es entonces una cuestión de resolver un sistema de ecuaciones lineales.
Relación con los pares de Wilf-Zeilberger
El algoritmo de Gosper se puede utilizar para descubrir pares de Wilf-Zeilberger , donde existan. Suponga que F ( n + 1, k ) - F ( n , k ) = G ( n , k + 1) - G ( n , k ) donde F se conoce pero G no. Luego introduzca a ( k ): = F ( n + 1, k ) - F ( n , k ) en el algoritmo de Gosper. (Trate esto como una función de k cuyos coeficientes resultan ser funciones de n en lugar de números; todo en el algoritmo funciona en esta configuración). Si encuentra con éxito S ( k ) con S ( k ) - S ( k - 1) = a ( k ), entonces hemos terminado: este es el G requerido . Si no es así, no hay tal G .
Suma definida versus indefinida
El algoritmo de Gosper encuentra (cuando es posible) una forma cerrada hipergeométrica para la suma indefinida de términos hipergeométricos. Puede suceder que no exista tal forma cerrada, pero que la suma de todos n , o algún conjunto particular de valores de n, tenga una forma cerrada. Esta pregunta solo es significativa cuando los coeficientes son en sí mismos funciones de alguna otra variable. Entonces, suponga que a (n, k) es un término hipergeométrico tanto en n como en k : es decir, a ( n , k ) / a ( n - 1, k ) y a ( n , k ) / a ( n , k - 1) son funciones racionales de n y k . Entonces el algoritmo de Zeilberger y el algoritmo de Petkovšek se pueden utilizar para encontrar formas cerradas para la suma sobre k de un ( n , k ).
Historia
Bill Gosper descubrió este algoritmo en la década de 1970 mientras trabajaba en el sistema de álgebra computacional Macsyma en SAIL y MIT .
Otras lecturas
- Petkovšek, Marko ; Wilf, Herbert ; Zeilberger, Doron (1996). A = B . Página de inicio del libro "A = B" . AK Peters Ltd. ISBN 1-56881-063-6. Archivado desde el original el 11 de julio de 2019 . Consultado el 10 de enero de 2020 . [1] [2] [3]
- Gosper, Jr., Ralph William "Bill" (enero de 1978) [26 de septiembre de 1977]. "Procedimiento de decisión por suma hipergeométrica indefinida" (PDF) . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . Matemáticas. Xerox, Palo Alto Research Center, Palo Alto, California, EE. UU. 75 (1): 40–42. Archivado (PDF) desde el original el 12 de abril de 2019 . Consultado el 10 de enero de 2020 .
algoritmo / identidades de coeficientes binomiales / forma cerrada / cálculo simbólico / recurrencias lineales