2
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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