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.

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

1 Answer 1

Reset to default
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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .