# Techniques for bounding a sum

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

• 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
• 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

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