I was playing around with a problem and I obtained a certain combinatorial sum. I was wondering if there was a way to simplify or bound it.

I have a real valued function $f$, which satisfies $|f(x)| \ll x^{\alpha}$ and $|\sum_{j=i}^n f(j)| \ll n^{\beta}$, $\alpha, \beta > 0$.

The sum I want to bound is $$ S(n) = \sum_{j_1 + j_2 = n-2} f(j_1)f(j_2) - 2 \sum_{j_1 + j_2 = n-1} f(j_1)f(j_2) + \sum_{j_1 + j_2 = n} f(j_1)f(j_2). $$

I was also wondering if bound $S(n) \ll \max( n^{2 \alpha}, n^{2 \beta} )$ is a reasonable bound to expect or not. (Maybe this is too strong I'm not sure...) I would appreciate any help finding a bound for $S(n)$ or simplifying it somehow. Thank you very much.

  • $\begingroup$ How big are $\alpha, \beta?$ $\endgroup$ – Igor Rivin Apr 24 '14 at 18:44
  • $\begingroup$ Here they are fairly arbitrary, but $\alpha, \beta < 1$ $\endgroup$ – SJY Apr 24 '14 at 20:10

Your sum is just a few terms off from $\sum_{1 \lt j \lt n} (f(j)-f(j-1))(f(n-j)f(n-j-1))$, where hopefully I did not mess up the indices too much. This in turn "looks like it is majorized" by $\int (xn-x^2)^\alpha dx$, with bounds of integration I'm too lazy to figure out, but is in turn majorized by $Cn^{2\alpha+1}$ for some positive constant $C$ and assuming $\alpha$ plays nicely with the above estimates. (As $\alpha$ is positive, there shouldn't be problems.)

You can improve upon this by knowing more about $f(j)-f(j-1)$ for your application. (E.g. if this difference is an increasing function of j that is bounded by $j^\alpha$, a simpler but weak bound would be $n(n^2/4)^\alpha$.) I would appreciate knowing more about the motivation, and if I just unwound a reformulation of yours. If this is for a course, I would like to know more about the course.

Gerhard "Ask Me About Rough Guesstimates" Paseman, 2014.04.24

  • $\begingroup$ thank you for your answer. It was helpful! It was just a random question I was considering :) $\endgroup$ – SJY May 1 '14 at 22:27

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.