En matemáticas, una ecuación P-recursiva se puede resolver para soluciones polinomiales . Sergei A. Abramov en 1989 y Marko Petkovšek en 1992 describieron un algoritmo que encuentra todas las soluciones polinomiales de esas ecuaciones de recurrencia con coeficientes polinomiales. [1] [2] El algoritmo calcula un límite de grado para la solución en un primer paso. En un segundo paso, se usa un ansatz para un polinomio de este grado y los coeficientes desconocidos se calculan mediante un sistema de ecuaciones lineales . Este artículo describe este algoritmo.
En 1995, Abramov, Bronstein y Petkovšek demostraron que el caso del polinomio se puede resolver de manera más eficiente si se considera la solución en serie de potencias de la ecuación de recurrencia en una base de potencia específica (es decir, no en la base ordinaria). [3]
Otros algoritmos que calculan soluciones racionales o hipergeométricas de una ecuación de recurrencia lineal con coeficientes polinomiales también utilizan algoritmos que calculan soluciones polinomiales.
Dejar ser un campo de característica cero yuna ecuación de recurrencia de orden con coeficientes polinomiales , polinomio lado derecho y secuencia polinomial desconocida . además denota el grado de un polinomio (con para el polinomio cero) y denota el coeficiente principal del polinomio. Además deja
por dónde denota la caída factorial y el conjunto de enteros no negativos. Luego . Esto se llama un límite de grado para la solución polinomial. . Abramov y Petkovšek mostraron este límite. [1] [2] [3] [4]El algoritmo consiste en dos pasos. En un primer paso, se calcula el límite de grados . En un segundo paso un ansatz con un polinomio de ese grado con coeficientes arbitrarios en se hace y se conecta a la ecuación de recurrencia. Luego se comparan las diferentes potencias y un sistema de ecuaciones lineales para los coeficientes deestá configurado y resuelto. A esto se le llama el método coeficientes indeterminados . [5] El algoritmo devuelve la solución polinomial general de una ecuación de recurrencia.
algoritmo polynomial_solutions es entrada: ecuación de recurrencia lineal . salida: la solución polinomial general si hay alguna solución, de lo contrario falso. por hacer repetir con coeficientes desconocidos por Comparar coeficientes de polinomios y para obtener posibles valores para si hay valores posibles para luego devuelve la solución general si no, devuelve un final falso si
Aplicar la fórmula para el límite de grado en la ecuación de recurrencia
encima rendimientos . Por lo tanto, se puede usar un ansatz con un polinomio cuadrático con . Conectar este ansatz en la ecuación de recurrencia original conduce a Esto es equivalente al siguiente sistema de ecuaciones lineales con la solucion . Por lo tanto, la única solución polinomial es .