(I posted this [question on Math.SE][1] 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?

<HR>

The two Math.SE responses were 

 1. "I agree that logarithmic growth is what you need. The 'binomial average' of $f(n)$  should be about $f(n/2)$." (from Michael Lugo)
 2. A reformulation of the problem in terms of exponential generating functions.  (from Qiaochu Yuan)

  [1]: https://math.stackexchange.com/questions/8415/asymptotic-difference-between-a-function-and-its-binomial-average