# A closed form for $T_N = 1 + \sum\limits_{k=0}^{N-2}{(N-1-k)T_k}$?

I've narrowed down a problem I am working on to the following recurrence:

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

I'm stuck on how to close it up, or at least make it linear or $O(n\log n)$. Any clues as to what technique I can use to make the sum into a closed form?

-
Generating functions should work. See, for example, Wilf (math.upenn.edu/~wilf/DownldGF.html). – Qiaochu Yuan Aug 2 '12 at 0:41
Please avoid titles that are entirely in $\LaTeX$. – J. M. Aug 2 '12 at 2:25

First, consider the differences between consecutive values: We have \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*} Or in other words $T_{N+1} = \sum_{k=0}^N T_k$. Can you figure out the rest from there?
(Incidentally, one way of arriving at a good closed-form for your recurrence, or at least starting a guess, is just to start plugging in values! Quick calculation shows that $T_2=1+1\cdot T_0 = 2$, $T_3 = 1+2\cdot T_0 + 1\cdot T_1 = 4$, and $T_4 = 1+3\cdot T_0+2\cdot T_1+1\cdot T_2 = 8$, and that should lead pretty easily to a hypothesis about $T_N$; from there it's just a matter of proving your guess.)