(I posted this question on Math.SEquestion on Math.SE a few weeks ago. I got a few comments, but nothing definite, and so I thought I would try MO.)
The origin of this question is the identity $$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \left(H_n - \sum_{k=1}^n \frac{1}{k 2^k}\right),$$ where $H_n$ is the $n$th harmonic number.
Dividing by $2^n$, we have $$2^{-n} \sum_{k=0}^n \binom{n}{k} H_k = H_n - \sum_{k=1}^n \frac{1}{k 2^k}.$$
The sum on the left can now be interpreted as a weighted average of the harmonic numbers through $H_n$ - where the weights, of course, are the binomial coefficients. Thus the difference between $H_n$ and its "binomial average" (I'm guessing there's no term for this) is $$H_n - 2^{-n} \sum_{k=0}^n \binom{n}{k} H_k = \sum_{k=1}^n \frac{1}{k 2^k}.$$
The sum on the right is known to converge to $\ln 2$ as $n \to \infty$. (Substitute $-\frac{1}{2}$ into the Maclaurin series for $\ln (1+x)$.)
This leads me to my question:
Can we classify nonnegative functions $f(n)$ for which $$\lim_{n \to \infty} \left(f(n) - 2^{-n} \sum_{k=0}^n \binom{n}{k} f(k) \right)$$ is finite and nonzero?
It would seem that if $f$ increases sufficiently rapidly, then the limit would be $\infty$. This is the case with both $f(n) = a^n$ and $f(n) = n$. If $f$ decreases or is constant, then the limit is zero. If $f$ has basically logarithmic growth, then it seems the limit would behave as $H_n$. But can this be proved? And what about other sublinear, increasing functions?
The two Math.SE responses were
- "I agree that logarithmic growth is what you need. The 'binomial average' of $f(n)$ should be about $f(n/2)$." (from Michael Lugo)
- A reformulation of the problem in terms of exponential generating functions. (from Qiaochu Yuan)
