# Bound for a combinatorial sum

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.

• How big are $\alpha, \beta?$ – Igor Rivin Apr 24 '14 at 18:44
• Here they are fairly arbitrary, but $\alpha, \beta < 1$ – 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.