Una forma cerrada para $T_N = 1 + \sum\limits_{k=0}^{N-2}{(N-1-k)T_k}$ ?

Question

He reducido un problema en el que estoy trabajando a la siguiente recurrencia:

$$\begin{align*} T_0 &= T_1 = 1\\ T_N &= 1 + \sum_{k=0}^{N-2}{(N-1-k)T_k} \end{align*}$$

Estoy atascado en cómo cerrarlo, o al menos hacerlo lineal o $O(n\log n)$ . ¿Alguna pista sobre qué técnica puedo utilizar para convertir la suma en una forma cerrada?

Answer 1

En primer lugar, consideremos las diferencias entre valores consecutivos: Tenemos $$\begin{align*}T_{N+1}-T_N &= \left(\sum_{k=0}^{N-1}(N-k)T_k\right)-\left(\sum_{k=0}^{N-2}(N-1-k)T_k\right) \\ &= \bigl(N-(N-1)\bigr)T_{N-1} + \sum_{k=0}^{N-2}\biggl((N-k)-(N-1-k)\biggr)T_k \\ &= T_{N-1}+\sum_{k=0}^{N-2}T_k \\ &= \sum_{k=0}^{N-1}T_k\end{align*}$$ O lo que es lo mismo $T_{N+1} = \sum_{k=0}^N T_k$ . ¿Puedes deducir el resto a partir de ahí?

(Por cierto, una forma de llegar a una buena forma cerrada para la recurrencia, o al menos de empezar a hacer conjeturas, es simplemente empezar a introducir valores). Un cálculo rápido muestra que $T_2=1+1\cdot T_0 = 2$ , $T_3 = 1+2\cdot T_0 + 1\cdot T_1 = 4$ y $T_4 = 1+3\cdot T_0+2\cdot T_1+1\cdot T_2 = 8$ y eso debería llevarnos fácilmente a una hipótesis sobre $T_N$ ; a partir de ahí sólo es cuestión de probar tu conjetura).