¿Cuándo es una recurrencia la suma de los poderes de las raíces de un polinomio?

Question

Newton fórmula permite calcular la suma de $S_n(P)$ de la $n$th potencias de las raíces de un determinado monic polinomio $P$ sin encontrar las raíces de forma explícita. (Esto funciona incluso cuando las raíces mismas no tienen una forma cerrada.) Si el polinomio es de $\mathbb{Z}[x]$, entonces la suma es un número entero; además, la secuencia de $(S_n)^\infty_{n=1}$ es una recurrencia lineal homogénea de orden $\deg(P).$

Estoy interesado en la transformación de este en torno a: dada una recurrencia lineal homogénea y un entero secuencia $(x_n)^\infty_{n=1}$ la satisfacción de esta recurrencia, ¿cómo puedo saber si hay un monic entero polinomio $P$ tal que $x_n$ es la suma de los $n$th potencias de las raíces de $P$? (Si es así, encontrar un polinomio es también de interés.)

Answer 1

Si el polinomio en el denominador de las funciones generadoras tiene solo raíces simples (es decir, raíces con multiplicidad 1), una descomposición parcial total de la función generadora solo tiene los términos$\sim 1/(x-r)$ con las raíces$r$, y reemplazando estos términos por sus series geométricas muestran que la serie original tiene la forma requerida (palabra clave: fórmula de Binet). Para raíces de orden superior, la descomposición de fracciones parciales también tiene otros términos.