(I posted this [question on Math.SE](https://math.stackexchange.com/questions/8415/asymptotic-difference-between-a-function-and-its-binomial-average) 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 


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)



Asymptotic difference between a function and its "binomial average"
The function $f(n)$ must be $\Theta (\log n)$. **Update:** As Didier Piau points out in the comments, we can say something stronger: $\frac{f(n)}{\log\_2 n} \to L$ as $n \to \infty$. See the update at the end of the argument. 


Suppose, for some positive $L$ (the negative case is similar), $$\lim\_{n \to \infty} \left(f(n) - 2^{-n} \sum\_{k=0}^n \binom{n}{k} f(k) \right) = L.$$
Thus $$f(n) = L + r(n) + 2^{-n} \sum\_{k=0}^n \binom{n}{k} f(k)$$ for some function $r(n)$ such that $r(n) \to 0$ as $n \to \infty$. This gives us a recurrence relation for $f(n)$. Since $r(n) \to 0$, $L + r(n) > 0$ for all sufficiently large $n$. So, for all sufficiently large $n$, there exist positive constants $C$ and $D$ such that $C < L + r(n) < D$. Since the initial terms in the function eventually become negligible in determining the value of $f(n)$ via the recurrence relation, there exist functions $g(n)$ and $h(n)$ such that for all sufficiently large $n$, $g(n) \leq f(n) \leq h(n)$ and $g(n)$ and $h(n)$ satisfy 
$$g(n) = C + 2^{-n} \sum\_{k=0}^n \binom{n}{k} g(k),$$
$$h(n) = D + 2^{-n} \sum\_{k=0}^n \binom{n}{k} h(k).$$


So the problem reduces to showing that $g(n)$ and $h(n)$ are $\Theta (\log n)$. The argument is the same for both.


There are some different ways to do this; my favorite is to interpret the $g(n)$ recurrence probabilistically. Suppose we start at time $g(0)$, we flip a set of $n$ coins simultaneously each round, and it takes $C$ time units to do one round of flips. When a coin turns up heads for the first time, we cease flipping it. Let $T(n)$ be the time at which the last coin to achieve its first head does so. To find $E[T(n)]$, condition on the number of coins that achieve heads in the first round of flips. This yields $$E[T(n)] = C + 2^{-n} \sum\_{k=0}^n \binom{n}{k} E[T(n-k)] = C + 2^{-n} \sum\_{k=0}^n \binom{n}{k} E[T(k)].$$ Thus $g(n) = E[T(n)]$.


Another way to view $T(n)$ is that it is $g(0) + C M\_n$, where $M\_n = \max\{X\_1, X\_2, \ldots, X\_n\}$ and the $X\_i$'s are independent and identically distributed geometric $(1/2)$ random variables. (Each geometric random variable models the first time a head appears.) Thus $g(n) = g(0) + C E[M\_n]$. It is known that $\frac{H\_n}{\log 2} \leq E[M\_n] \leq \frac{H\_n}{\log 2} + 1$ and, more precisely, that $E[M\_n]$ is logarithmically summable to $\frac{H\_n}{\log 2} + \frac{1}{2}$. (See, for example, Bennett Eisenberg's paper "On the expectation of the maximum of IID geometric random variables," *Statistics and Probability Letters* 78 (2008) 135-143. See also this MO question, "[What is the Expected Maximum out of a Sample (size $n$) from a Geometric Distribution](https://mathoverflow.net/questions/41604/what-is-the-expected-maximum-out-of-a-sample-size-n-from-a-geometric-distributi/)?")


Thus $g(n) = \frac{C}{\log 2} \log n + O(1)$, which means that $h(n) = \frac{D}{\log 2} \log n + O(1)$ and $f(n) = \Theta (\log n)$.


**Update:** Given $\epsilon > 0$, if we take take $C > 0$ such that $L - \epsilon \leq C < L$ and $D = L + \epsilon$, this argument shows that 
$$L - \epsilon + O\left(\frac{1}{\log n}\right) \leq \frac{f(n)}{\log\_2 n} \leq L + \epsilon + O\left(\frac{1}{\log n}\right).$$


Thus, as $n \to \infty$, $\frac{f(n)}{\log\_2 n} \to L.$


For some other ideas that pertain to this result, including what are effectively some alternative derivations, see Pradipta's recent MO question, "[Coin Flipping and a Recurrence Relation](https://mathoverflow.net/questions/55625/coin-flipping-and-a-recurrence-relation)". In fact, reading Pradipta's question and some of its answers gave me the ideas needed to construct this argument! So, thanks go to Pradipta, Didier Piau, Emil Jeřábek, and Louigi Addario-Berry.


