Algoritmo de Gosper

En matemáticas , el algoritmo de Gosper , debido a Bill Gosper , es un procedimiento para hallar 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 a ( n ) es en sí mismo un término hipergeométrico, y dada la fórmula para a ( n ), el algoritmo de Gosper halla que para S ( n ).

Paso 1: Hallar un polinomio p tal que, escribiendo b ( n ) = a ( n )/ p ( n ), la razón b ( n )/ b ( n  − 1) tenga 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 j = 0, 1, 2, ... . (Esto siempre es posible, sea o no la serie sumable en forma cerrada).

Paso 2: Hallar 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 ƒ con esta propiedad; de hecho, siempre debe ser un polinomio, y se puede hallar un límite superior para su grado. Determinar ƒ (o encontrar que no existe tal ƒ ) es entonces una cuestión de resolver un sistema de ecuaciones lineales. ^[1]

El algoritmo de Gosper puede utilizarse para descubrir pares de Wilf–Zeilberger , cuando existan. Supongamos que F ( n  + 1,  k ) −  F ( n ,  k ) = G ( n ,  k  + 1) −  G ( n ,  k ) donde F es conocida 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 este contexto). Si encuentra con éxito S ( k ) con S ( k ) −  S ( k  − 1) = a ( k ), entonces hemos terminado: este es el G requerido . Si no, no existe tal G .

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 sobre todos los n , o algún conjunto particular de valores de n, tenga una forma cerrada. Esta pregunta solo tiene sentido cuando los coeficientes son en sí mismos funciones de alguna otra variable. Por lo tanto, supongamos 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 pueden usarse para encontrar formas cerradas para la suma sobre k de a ( n ,  k ).

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

• Gosper, Jr., Ralph William "Bill" (enero de 1978) [1977-09-26]. "Procedimiento de decisión para la suma hipergeométrica indefinida" (PDF) . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . Matemáticas. 75 (1). Xerox, Palo Alto Research Center, Palo Alto, California, EE. UU.: 40–42. Bibcode :1978PNAS...75...40G. doi : 10.1073/pnas.75.1.40 . PMC  411178 . PMID  16592483. Archivado (PDF) desde el original el 2019-04-12 . Consultado el 2020-01-10 . algoritmo / identidades de coeficientes binomiales / forma cerrada / computación simbólica / recurrencias lineales