Algoritmo de Gosper

En matemáticas, el algoritmo de Gosper es un método para encontrar sumas de términos hipergeométricos que son términos hipergeométricos por sí mismos. Esto es: se supone que tenemos a(1) + ... + a(n) = S(n) - S(0), donde S(n) es un término hipergeométrico (i.e., S(n+1)/S(n) es una función racional de n); entonces, necesariamente a(n) es en sí mismo un término hipergeométrico, y, dada la fórmula para a(n), el algoritmo de Gosper lo encuentra para S(n).

Esbozo del algoritmo

Paso 1: Encontrar un polinomio p tal que, escribiendo b(n) = a(n)/p(n) , la proporción b(n)/b(n-1) tiene la forma q(n)/r(n) donde q y r son polinomios y ningún q(n) tiene un factor no trivial con r(n+j) para cualquier j entero no negativo. Lo cual es siempre posible, sea o no la serie u de una forma cerrada.

Paso 2: Encontrar un polinomio f tal que S(n) = q(n+1)/p(n) f(n) a(n). Si la serie es sumable de una forma cerrada, entonces claramente existe una función racional f con esta propiedad; de hecho, debe ser siempre un polinomio y se puede encontrar una cota superior para su grado. Determinar f, o encontrar que no existe tal f, es un cuestión de resolver un sistema de ecuaciones lineales.

Relación con los pares Wilf–Zeilberger

El algoritmo de Gosper puede ser usado para descubrir un par Wilf-Zeilberger, donde existan. Suponemos que F(n+1, k) − F(n, k) = G(n, k+1) − G(n, k) dónde F es conocido, pero G no lo es. Entonces definimos a(k) := F(n + 1, k) − F(n, k) en el propio algoritmo de Gosper. Si encontramos S(k) verificando S(k) − S(k-1) = a(k), entonces hemos terminado, esto es, hemos encontrado el G que queríamos . Si no, hay no tal G.

Sumatorio definido contra indefinido

EL algoritmo de Gosper encuentra, cuando es posible, una forma hipergeométrica cerrada para la suma indefinida de términos hipergeométricos. Puede pasar que tal forma cerrada no exista, pero que la suma sobre todos los términos de n (o algunos en particular) tenga una forma cerrada. Esta cuestión solo tiene sentido cuando los coeficientes son funciones de alguna otra variable. Así, supongamos que a(n, k) es un término hipergeométrico sobre n y k. Entonces el algoritmo de Zeilberger y el algoritmo de Petkovšek puede ser usado para encontrar formas cerradas para la suma sobre k de a(n, k).

Historia

Bill Gosper descubrió este algoritmo la década de 1970 mientras trabajaba en el sistema de álgebra computacional Macsyma en el Laboratorio de I.A. de la Universidad de Stanford y en el MIT.

Lectura más lejana

• Marko Petkovšek, Herbert Wilf y Doron Zeilberger, A = B, AK Peters 1996, ISBN 1-56881-063-6. Texto completo en línea.[1]
• [www.pnas.org/cgi/reprint/75/1/40.pdf Artículo] de Gosper en 1997 en PNAs informando sobre el algoritmo.

• Datos: Q5587427