Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Generating functions should work. See, for example, Wilf ( – Qiaochu Yuan Aug 2 '12 at 0:41
Please avoid titles that are entirely in $\LaTeX$. – J. M. Aug 2 '12 at 2:25
up vote 5 down vote accepted

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.)

share|cite|improve this answer
I made a mistake sorry: See here:… – Andrew Tomazos Aug 2 '12 at 2:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.