¿Es posible convertir un polinomio en una relación de recurrencia? Si es así, ¿cómo?

Question

Llevo bastante tiempo intentando hacerlo, pero en general la información parcialmente relevante que he podido encontrar en internet sólo se refería a la pregunta "¿Cómo se convierte una relación de recurrencia en... bueno, una relación de no recurrencia?"

Empecemos con un ejemplo sencillo: $f(n) = 34n^3+51n^2+27n+5$ . ¿Cómo podemos encontrar $f_{n}$ ? Me gustaría que esto se resolviera por analogía con lo siguiente: Considere $g(n)=n^6$ Entonces podemos encontrar la fórmula de recursión: $g_n=((g_{n-1})^{1/6}+1)^6$ . ¿Qué pasa con $f_{n}$ ?

Podríamos generalizar esta cuestión de varias maneras. Por ejemplo, ¿es (también) posible convertir un polinomio infinito, como la expansión en serie de Taylor de una fórmula trigonométrica, en una fórmula de recursión? Además, ¿qué ocurre cuando permitimos que los coeficientes del polinomio sean reales e incluso complejos?

Gracias,

Max

Pregunta adicional: ¿Qué utilidad tienen las "funciones generadoras" en este contexto?

Answer 1

Cualquier polinomio $f(n)$ de grado $d$ sobre un anillo conmutativo arbitrario, satisface la recursión

$$\sum_{k=0}^{d+1} (-1)^{d+1-k} {d+1 \choose k} f(x+k) = 0$$

para cualquier $x$ . Se trata de una aplicación del método de diferencias finitas . En términos de funciones generadoras, dice que

$$\sum_{n \ge 0} f(n) x^n = \frac{P(x)}{(1 - x)^{d+1}}$$

para algún polinomio $P(x)$ . Esto debería ser tratado a fondo en un libro como el de Wilf Generación de funcionalidades ; de lo contrario, lo discuto en mi notas sobre las funciones generadoras . En general, si $f(n)$ tiene una función generadora de la forma $\frac{P(x)}{Q(x)}$ donde $P$ es un polinomio, entonces los coeficientes de $Q$ describen una recurrencia que $f(n)$ finalmente se satisface.

No estoy seguro de entender su pregunta más general. ¿Tiene alguna aplicación específica en mente?

Answer 2

Max, sólo detallo la respuesta de Qiaochu, usando Pari/GP. Primero define la función
$ f(x) = 34*x^3+51*x^2+27*x+5$

Entonces la primera idea para descomponer f en una recursión de 2 términos es
$ f(x)-1*f(x-1) $
Pari/GP: $ <out> = 102*x^2 + 10 $

Así que el resultado ya es un polinomio reducido. Ahora reste de esto $f(x-1)-f(x-2) $ porque éste será un polinomio del mismo grado, sólo que "desplazado" por algunos coeficientes.

Esto da
$ f(x)-2*f(x-1)+f(x-2) $
Pari/GP: $ <out> = 204*x - 102 $

De nuevo el polinomio resultante es de orden reducido. Ahora terminamos restando $ f(x-1)-2*f(x-2)+f(x-3) $

Lo conseguimos:
$ f(x)-3*f(x-1)+3*f(x-2)-f(x-3) $
Pari/GP: $ <out> = 204 $

Ahora sólo tenemos una expresión constante. Terminamos y escribimos, reordenando los términos:

$ f(x) = 3*f(x-1)-3*f(x-2)+f(x-3)+204 $

[actualización] Para completar se puede aumentar el grado. Según la respuesta/comentario de Qiaochu podemos restar de nuevo el polinomio desplazado x-1 $ f(x-1)-3*f(x-2)+3*f(x-3)-f(x-4) $ y, por supuesto, conseguir

$ f(x)-4*f(x-1)+6*f(x-2)-4*f(x-3)+f(x-4) $
Pari/GP: $ <out> = 0 $

completar la respuesta $ f(x) = 4*f(x-1)-6*f(x-2)+4*f(x-3)-f(x-4) $

[fin de la actualización]

Answer 3

Ampliar $f(n+1)$ y obtendrás $f(n+1)=f(n)+g(n)$ para algunos $g$ . Para $f(n)=34n^3+51n^2+27n+5$ , se obtiene $f(n+1)=f(n)+102n^2+204n+112$ .

Answer 4

HINT $\rm\ \ \Delta\ f \ :=\ f(n+1) - f(n)\ $ reduce $\rm\ d = deg\ f\:,\ $ así que $\rm\ \Delta^{d+1}\ f\ =\ 0\ $ produce una recurrencia para $\rm\: f\:$ . Las funciones que admiten recurrencias se conocen como P-recursivo . Google función holonómica para conocer su rica teoría, que tiene amplias aplicaciones.