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

  • $\begingroup$ 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. $\endgroup$ – Joe Oct 16 '12 at 21:58
  • $\begingroup$ 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}$. $\endgroup$ – picakhu Oct 16 '12 at 21:59
  • $\begingroup$ There's really nothing I can tell you without at least some information about the formula. $\endgroup$ – Alexander Gruber Oct 16 '12 at 22:01
  • 1
    $\begingroup$ If stuff is messy, won't the integrals be messy as well? $\endgroup$ – Hagen von Eitzen Oct 16 '12 at 22:01
  • $\begingroup$ @HagenvonEitzen my idea for using integrals came from a simple proof bounding the harmonic series in the coupon collector problem. $\endgroup$ – Joe Oct 16 '12 at 22:44

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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