Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
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
add comment

1 Answer 1

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|improve this answer
    
I made a mistake sorry: See here: math.stackexchange.com/questions/177856/… –  Andrew Tomazos Aug 2 '12 at 2:00
add comment

Your Answer

 
discard

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.