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
    @filmor thanks, that's helpful2012-10-18

1 Answers 1

2

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.