0
$\begingroup$

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

  • 0
    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.2012-10-16
  • 0
    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}$.2012-10-16
  • 0
    There's really nothing I can tell you without at least some information about the formula.2012-10-16
  • 1
    If stuff is messy, won't the integrals be messy as well?2012-10-16
  • 0
    @HagenvonEitzen my idea for using integrals came from a simple proof bounding the harmonic series in the coupon collector problem.2012-10-16
  • 0
    I'm looking for more general ideas, like these: http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap03.htm2012-10-18
  • 0
    How about the [Euler MacLaurin Formula](http://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula#Asymptotic_expansion_of_sums)? Together with some integral representations of special functions you could calculate many asymptotics.2012-10-18
  • 0
    @filmor thanks, that's helpful2012-10-18

1 Answers 1