The following seems true for a wide range of functions: $\sum_{k=1}^n f(k)f(n-k) = n f^2(n/2) (1 + o(1))$

Question

I haven't worked out all the details yet, but it seems to be true for the following functions:

• $f(k) = 1$
• $f(k) = 1/k!$
• $f(k) = a^k$
• $f(k) = 1/\log(k+1)$

What are the conditions on $f$ for this to be true? It sounds like a fairly general result that should be easy to prove. Sums like these are related to the discrete self-convolution operator, so I'm pretty sure the result mentioned here must be well known.

Update: A weaker result that applies to a broader class of functions is the following: $$\sum_{k=1}^n f(k)f(n-k) = O\Big(n f^2(\frac{n}{2})\Big).$$ Is it possible to find a counter-example, with a function $f$ that is smooth enough and in wide use?

Answer 1

If you think the error term is produced from approximation of an integral: $$\frac{1}{n} \int_0^n f*f=\frac{1}{f^2(n/2)}$$ That means you should search for functions that mean of their convolution to themselves is equal to inverse of square of them at mid point of interval, that in fact meet each other. There is two natural points that many of functions close to satisfy them:

1) Get mean value at mid point.

2) Since $f$ convulses with itself, the $f^2$ is a good candidate for mean.

So you should more think about functions that satisfy the inverse of that mean we expect more, $1/f^2(n/2)$ instead of $f^2(n/2)$.

Answer 2

This is not an answer, but rather an upper bound. Using the Cauchy-Schwartz inequality, it is easy to obtain $$\sum_{k=1}^n f(k)f(n-k)\leq \sum_{k=0}^n f^2(k)\sim \int_0^nf^2(x) dx.$$

For a full solution, consider two independently and identically distributed random variables $X_n, Y_n$ with $P(X_n =k) = P(Y_n=k) \propto f(k)$ for $k=0, 1, \cdots, n$. This assumes that $f\geq 0$. Then $$\sum_{k=1}^n f(k)f(n-k)\approx P(X_n+Y_n \leq n) .$$

The distribution of $X_n + Y_n$ can be obtained using the convolution theorem.

Answer 3

$\sum_{k=0}^n f(k)f(n-k) = O\Big(n f^2(\frac{n}{2})\Big)$ doesn't hold when $f(0) \ne 0$ and $f(n)$ grows much faster than $f(n/2)^2$ for example with $f(n)= e^{n!}$