¿Por qué debemos sospechar que el % de repetición $T(n) = T(n-1) + n(n-1)$cumple una identidad polinómica?

Question

En la cuestión de los Algoritmos: Recurence Relación, el autor le preguntó acerca de la relación de recurrencia $$T(n) = T(n-1) + n(n-1)$$ and one of the answers proposed assuming $T(n)$ es el polinomio, entonces, manipulando la ecuación para obtener los coeficientes.

Pregunta: ¿Qué razón hay para sospechar que esta recurrencia satisface un polinomio de identidad? Y ¿cómo podemos aplicar esto a lineal recurrencias en general?

Los Números de Fibonacci, por ejemplo, en lugar de satisfacer a una solución exponencial. Por lo tanto, si hemos intentado ajustar un polinomio de solución, que no iba a funcionar.

Answer 1

Deje $a_0,a_1,a_2,a_3,\dots$ ser una secuencia. Deje $b_0,b_1,b_2,b_3,\dots$ ser la secuencia de (primera), las diferencias de las $a_i$. Por lo $b_i=a_{i+1}-a_i$.

En general, si la secuencia de $b_0,b_1,b_2,\dots$ está dado por $b_i=P(i)$ donde $P$ es un polinomio de grado $k$, entonces la secuencia original es dada por un polinomio de grado $k+1$. Este es un resultado en un grande y útil sujeto llamado el cálculo de las diferencias finitas.

Es análogo al resultado que si la derivada de una función es un polinomio de grado $k\ge 0$, entonces la función es un polinomio de grado $k+1$.

Por lo tanto, automáticamente, la secuencia del post es dada por un polinomio de grado $3$.

Answer 2

No del todo una respuesta sino una explicación parcial: la ecuación puede ser reescrita como $T(n)-T(n-1) = n(n-1)$ (tenga en cuenta que la serie de la ecuación no puede ser fácilmente 'borra' en esto de la moda); sabemos si $p(x)$ es el polinomio de grado $n$, la diferencia finita $\Delta p(x) \equiv p(x+1)-p(x)$ es el polinomio de grado $n-1$ (esto no es muy difícil de probar usando el teorema del binomio y hace una bonita expresión — que aún debe ser capaz de obtener una forma explícita para los coeficientes de $\Delta p(x)$ si se intenta), así que tiene sentido para intentar 'invertir' esto y trabajar con el supuesto de que $T()$ es de tercer grado del polinomio para el problema dado.

De hecho, los llamados polinomios de Bernoulli dar un enfoque directo a la solución de este problema: los que sirven para 'invertir' la diferencia finita de operador para monomials $x^n$ (en otras palabras, si $B_{n+1}(x)$ es el orden de $n+1$ Bernoulli polinomio, entonces tenemos $\Delta B_{n+1}(x) = x^n$, hasta un pequeño factor multiplicativo) de la misma manera que regular monomials hacer la misma cosa para los productos derivados. Ya que la diferencia finita de operador es lineal (es decir, $\Delta(ap_1(x)+bp_2(x)) = a\Delta p_1(x)+b\Delta p_2(x)$), una vez que entendemos cómo calcular la inversa de la diferencia finita de operación para cada término de un polinomio, podemos calcular la inversa en el polinomio como un todo.