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 have a very messy function. It consists sums four levels deep, and the inner-most term is itself quite messy.

$$ \sum \sum \sum \sum (\mbox{stuff})$$

I can't find a closed form for this function. However, I don't need an exact closed form; I'm only interested in the asymptotic behavior. One idea I have is to approximate the sum using integrals. Would that work? What are some other techniques I can use to upper and/or lower bound a function when the sum is too messy to get into closed form?

Edit: one of the formulas I'm working with looks like this: $$\sum_{x_1 = 1}^n \sum_{x_2 = 1}^n \sum_{y_1 = 1}^n \sum_{y_2=1}^n \left( n^{-2} \left(\frac{n- y_2 + y_1 - 1}{n}\right)^{x_2 - x_1 - 1} \right)$$

share|improve this question
    
I didn't include the formula because I don't want someone to simplify a specific formula for me; I want to know general techniques for asymptotically bounding a sum of sums. –  Joe Oct 16 '12 at 21:58
    
I think it does depend on what is (stuff). There is no simple way to do it, because each of the $\Sigma$ can bring about a lot of complexity, for example, just imagine $\Sigma_{prime}$. –  picakhu Oct 16 '12 at 21:59
    
There's really nothing I can tell you without at least some information about the formula. –  Alexander Gruber Oct 16 '12 at 22:01
1  
If stuff is messy, won't the integrals be messy as well? –  Hagen von Eitzen Oct 16 '12 at 22:01
    
@HagenvonEitzen my idea for using integrals came from a simple proof bounding the harmonic series in the coupon collector problem. –  Joe Oct 16 '12 at 22:44
show 3 more comments

1 Answer

For the formula you post, the outer two sums are geometric series and can be summed that way. Then you can combine $y_1-y_2$ to give $2n+1$ terms (one of which is zero) instead of $n^2$ and your problem is linear in $n$ instead of fourth order.

share|improve this answer
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.