Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $H_n$ denote the $n$th harmonic number; i.e., $H_n = \sum\limits_{i=1}^n \frac{1}{i}$. I've got a couple of proofs of the following limiting expression, which I don't think is that well-known: $$\lim_{n \to \infty} \left(H_n - \frac{1}{2^n} \sum_{k=1}^n \binom{n}{k} H_k \right) = \log 2.$$ I'm curious about other ways to prove this expression, and so I thought I would ask here to see if anybody knows any or can think of any. I would particularly like to see a combinatorial proof, but that might be difficult given that we're taking a limit and we have a transcendental number on one side. I'd like to see any proofs, though. I'll hold off from posting my own for a day or two to give others a chance to respond first.

(The probability tag is included because the expression whose limit is being taken can also be interpreted probabilistically.)


(Added: I've accepted Srivatsan's first answer, and I've posted my two proofs for those who are interested in seeing them.

Also, the sort of inverse question may be of interest. Suppose we have a function $f(n)$ such that $$\lim_{n \to \infty} \left(f(n) - \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} f(k) \right) = L,$$ where $L$ is finite and nonzero. What can we say about $f(n)$? This question was asked and answered a while back; it turns out that $f(n)$ must be $\Theta (\log n)$. More specifically, we must have $\frac{f(n)}{\log_2 n} \to L$ as $n \to \infty$.)

share|improve this question
3  
Well, this is very rough argument and I think one can make this precise. (Please don't boo me if this is to your taste :)) By central limit theorem or just plain quantitative estimates, one can see that the binomial distribution $2^{-n}\binom{n}{k}$ is concentrated around $k=n/2$. Plugging this value naively in the limit expression, we have $H_n - H_{n/2} \approx \log n + \gamma - \log (n/2) - \gamma = \log 2$. –  Srivatsan Sep 11 '11 at 4:02
    
@Srivatsan: I like that argument for the intuition. But, yes, for a full answer I would like to see something more precise. :) –  Mike Spivey Sep 11 '11 at 4:21
    
I think that more people in a position to contribute insight (including combinatorial solutions, which are sought in the question) will see the problem if it is tagged [probability]. Also, since the question requests [combinatorics] that tag does seem to apply. –  zyx Sep 12 '11 at 5:45
    
@zyx: Fair enough. I'll add both tags. –  Mike Spivey Sep 12 '11 at 15:34
    
Thanks to all for the answers! I got what I wanted by asking this question; namely, a deeper understanding of why this limiting result holds. I'm accepting Srivatsan's first answer because I like how it formalizes the intuition that the limit should be $\log 2$ - as the summation should be close to $\log n/2$. –  Mike Spivey Sep 14 '11 at 5:41

6 Answers 6

up vote 12 down vote accepted

I made an quick estimate in my comment. The basic idea is that the binomial distribution $2^{−n} \binom{n}{k}$ is concentrated around $k= \frac{n}{2}$. Simply plugging this value in the limit expression, we get $H_n−H_{n/2} \sim \ln 2$ for large $n$. Fortunately, formalizing the intuition isn't that hard.

Call the giant sum $S$. Notice that $S$ can be written as $\newcommand{\E}{\mathbf{E}}$ $$ \sum_{k=0}^{\infty} \frac{1}{2^{n}} \binom{n}{k} (H(n) - H(k)) = \sum_{k=0}^{\infty} \Pr[X = k](H(n) - H(k)) = \E \left[ H(n) - H(X) \right], $$ where $X$ is distributed according to the binomial distribution $\mathrm{Bin}(n, \frac12)$. We need the following two facts about $X$:

  • With probability $1$, $0 \leqslant H(n) - H(X) \leqslant H(n) = O(\ln n)$.
  • From the Bernstein inequality, for any $\varepsilon \gt 0$, we know that $X$ lies in the range $\frac{1}{2}n (1\pm \varepsilon)$, except with probability at most $e^{- \Omega(n \varepsilon^2) }$.

Since the function $x \mapsto H(n) - H(x)$ is monotone decreasing, we have $$ S \leqslant \color{Red}{H(n)} \color{Blue}{-H\left( \frac{n(1-\varepsilon)}{2} \right)} + \color{Green}{\exp (-\Omega(n \varepsilon^2)) \cdot O(\ln n)}. $$ Plugging in the standard estimate $H(n) = \ln n + \gamma + O\Big(\frac1n \Big)$ for the harmonic sum, we get: $$ \begin{align*} S &\leqslant \color{Red}{\ln n + \gamma + O \Big(\frac1n \Big)} \color{Blue}{- \ln \left(\frac{n(1-\varepsilon)}{2} \right) - \gamma + O \Big(\frac1n \Big)} +\color{Green}{\exp (-\Omega(n \varepsilon^2)) \cdot O(\ln n)} \\ &\leqslant \ln 2 - \ln (1- \varepsilon) + o_{n \to \infty}(1) \leqslant \ln 2 + O(\varepsilon) + o_{n \to \infty}(1). \tag{1} \end{align*} $$

An analogous argument gets the lower bound $$ S \geqslant \ln 2 - \ln (1+\varepsilon) - o_{n \to \infty}(1) \geqslant \ln 2 - O(\varepsilon) - o_{n \to \infty}(1). \tag{2} $$ Since the estimates $(1)$ and $(2)$ hold for all $\varepsilon > 0$, it follows that $S \to \ln 2$ as $n \to \infty$.

share|improve this answer
    
Nice. Thanks for the analysis-style argument. –  Mike Spivey Sep 11 '11 at 13:11

Here's a different proof. We will simplify the second term as follows: $$ \begin{eqnarray*} \frac{1}{2^n} \sum\limits_{k=0}^n \left[ \binom{n}{k} \sum\limits_{t=1}^{k} \frac{1}{t} \right] &=& \frac{1}{2^n} \sum\limits_{k=0}^n \left[ \binom{n}{k} \sum\limits_{t=1}^{k} \int_{0}^1 x^{t-1} dx \right] \\ &=& \frac{1}{2^n} \int_{0}^1 \sum\limits_{k=0}^n \left[ \binom{n}{k} \sum\limits_{t=1}^{k} x^{t-1} \right] dx \\ &=& \frac{1}{2^n} \int_{0}^1 \sum\limits_{k=0}^n \left[ \binom{n}{k} \cdot \frac{x^k-1}{x-1} \right] dx \\ &=& \frac{1}{2^n} \int_{0}^1 \frac{\sum\limits_{k=0}^n \binom{n}{k} x^k- \sum\limits_{k=0}^n \binom{n}{k}}{x-1} dx \\ &=& \frac{1}{2^n} \int_{0}^1 \frac{(x+1)^n- 2^n}{x-1} dx. \end{eqnarray*} $$

Make the substitution $y = \frac{x+1}{2}$, so the new limits are now $1/2$ and $1$. The integral then changes to: $$ \begin{eqnarray*} \int_{1/2}^1 \frac{y^n- 1}{y-1} dy &=& \int_{1/2}^1 (1+y+y^2+\ldots+y^{n-1}) dy \\ &=& \left. y + \frac{y^2}{2} + \frac{y^3}{3} + \ldots + \frac{y^n}{n} \right|_{1/2}^1 \\ &=& H_n - \sum_{i=1}^n \frac{1}{i} \left(\frac{1}{2} \right)^i. \end{eqnarray*} $$ Notice that conveniently $H_n$ is the first term in our function. Rearranging, the expression under the limit is equal to: $$ \sum_{i=1}^n \frac{1}{i} \left(\frac{1}{2} \right)^i. $$ The final step is to note that this is just the $n$th partial sum of the Taylor series expansion of $f(y) = -\ln(1-y)$ at $y=1/2$. Therefore, as $n \to \infty$, this sequence approaches the value $$-\ln \left(1-\frac{1}{2} \right) = \ln 2.$$

ADDED: As Didier's comments hint, this proof also shows that the given sequence, call it $u_n$, is monotonoic and is hence always smaller than $\ln 2$. Moreover, we also have a tight error estimate: $$ \frac{1}{n2^n} < \ln 2 - u_n < \frac{2}{n2^n}, \ \ \ \ (n \geq 1). $$

share|improve this answer
1  
The same method shows that $H_n - \sum \binom{n}{k}p^k(1-p)^{n-k}H_k$ is the sum of the first $n$ terms of $-\log(1-y)$ at $y=(1-p)$. In the limit this is $-\log(p)$, consistent with the probability argument (which leads to integrating $dx/x$ on $[pn,n]$ or $[p,1]$), and demonstrating that convergence is exponential. Thanks for the illuminating proof. –  zyx Sep 13 '11 at 2:06
2  
This is similar to one of my two proofs. The difference is that I got to $\sum_{i=1}^n \frac{1}{i2^i}$ in another fashion. I think I like the way you got to $\sum_{i=1}^n \frac{1}{i2^i}$ better, though. Very nice. –  Mike Spivey Sep 13 '11 at 3:14
1  
+1. Quite nice. (No approximation till the very end, and this shows the difference between the $n$th term and the limit is one-sided and $\sim 1/(n2^n)$.) –  Did Sep 13 '11 at 5:40
    
@Didier Quite true. Yes, I am also particularly surprised at the exponential rate of convergence. It would seem natural to approximate $H_n$ by $\ln n + \gamma$, but even that error is too high. –  Srivatsan Sep 13 '11 at 5:46
2  
Yep. This is a linear combination of harmonic numbers whose sum of coefficients is (almost) zero, hence that some smaller terms in the asymptotic expansion of $H_n$ cancel is to be expected--maybe not that so many do. –  Did Sep 13 '11 at 5:57

Looking at $2^{-n}\binom{n}{k}$ as a probability distribution with mean $\frac{n}{2}$ and standard deviation $\frac{\sqrt{n}}{2}$ it is pretty easy to see that, as a Riemann sum $$ \begin{align} 2^{-n}\sum_{k=1}^n\binom{n}{k}H_k&\sim\sqrt{\frac{2}{\pi n}}\int_{-\infty}^\infty (\log(x)+\gamma)\;e^{-2(x-n/2)^2/n}\;\mathrm{d}x\\ &=\log(n/2)+\gamma+O\left(\frac{1}{\sqrt{n}}\right) \end{align} $$ Since $H_n\sim\log(n)+\gamma$, we get the difference to be $\log(2)$.

Let me attack this in a different way (though the former still works).

Using the asymptotic expansion for $H_n$, we get for $k\le n$, $$ H_n-H_k=-\log(k/n)+O\left(\frac{1}{k}\right)\tag{1} $$ Since we will be dealing with $O\left(\frac{1}{k}\right)$, notice that $$ \begin{align} 2^{-n}\sum_{k=1}^n\binom{n}{k}\frac{1}{k+1} &=2^{-n}\sum_{k=1}^n\binom{n+1}{k+1}\frac{1}{n+1}\\ &\le 2^{-n}\;2^{n+1}\frac{1}{n+1}\\ &=\frac{2}{n+1} \end{align} $$ Therefore, $$ 2^{-n}\sum_{k=1}^n\binom{n}{k}O\left(\frac{1}{k}\right)=O\left(\frac{1}{n}\right)\tag{2} $$ The Central Limit Theorem says that for any continuous $f$ on $[0,1]$, $$ \lim_{n\to\infty}\;2^{-n}\sum_{k=1}^n\binom{n}{k}f\left(\frac{k}{n}\right) = f\left(\frac{1}{2}\right)\tag{3} $$ To justify $(3)$, pick $\epsilon>0$ and find $\delta$ so that $\left|x-\frac{1}{2}\right|<\delta\Rightarrow\left|f(x)-f(\frac{1}{2})\right|<\epsilon$. Because the mean of $2^{-n}\binom{n}{k}$ is $\frac{n}{2}$ and the variance is $\frac{n}{4}$, the Central Limit Theorem says that we can pick a $\sigma$ big enough so that $$ \underset{|k-n/2|<\sigma\sqrt{n}/2}{2^{-n}\sum\binom{n}{k}}>1-\epsilon $$ for all $n$. Therefore, we choose an $n$ large enough so that $\sigma\sqrt{n}/2<n\delta$. $$ \begin{align} 2^{-n}\sum_{k=1}^n\binom{n}{k}\left|f\left(\frac{k}{n}\right)-f\left(\frac{1}{2}\right)\right| &\le \epsilon\;\max_{[0,n]}\left|f\left(\frac{k}{n}\right)-f\left(\frac{1}{2}\right)\right|\\ &+\max_{|k-n/2|<n\delta}\left|f\left(\frac{k}{n}\right)-f\left(\frac{1}{2}\right)\right|\\ &\le \epsilon\;\max_{[0,1]}\left|f\left(x\right)-f\left(\frac{1}{2}\right)\right|\\ &+\;\epsilon \end{align} $$

Finally, $$ \begin{align} H_n-2^{-n}\sum_{k=1}^n\binom{n}{k}H_k &=2^{-n}\sum_{k=1}^n\binom{n}{k}(H_n-H_k)\\ &=2^{-n-1}\sum_{k=1}^n\binom{n+1}{k+1}\;2\frac{k+1}{n+1}(H_n-H_k)\\ &=2^{-n-1}\sum_{k=1}^n\binom{n+1}{k+1}\left(-2\frac{k+1}{n+1}\log\left(\frac{k+1}{n+1}\right)+O\left(\frac{1}{k}\right)\right)\\ &=-2^{-n-1}\sum_{k=1}^n\binom{n+1}{k+1}\left(-2\frac{k+1}{n+1}\log\left(\frac{k+1}{n+1}\right)\right)+O\left(\frac{1}{n}\right)\\ &\to-2\;\frac{1}{2}\log(\frac{1}{2})\\ &=\log(2) \end{align} $$

share|improve this answer
1  
I have some concerns about your argument. The first step looks to me like an approximation of $E[H_X]$, where $X$ is binomial$(n,1/2)$, with $E[H_Y + O(1/n)]$, where $Y$ is $N(n/2,n/4)$. I agree that the normal approximation to the binomial is going to very good as $n$ gets large, but how well does that translate into approximating $E[f(X)]$ with $E[f(Y)]$? For example, $E[e^X] = ((e+1)/2)^n$, and $E[e^Y] = (\exp(5/8))^n$. Now, $(e+1)/2$ is very close to $\exp(5/8)$, but the difference is going to increase rapidly as $n$ gets large. –  Mike Spivey Sep 12 '11 at 3:27
1  
(Continued) I imagine that using $f(x) = \log x$ will give a much smaller error, but for a proof there should still be some discussion of that error. –  Mike Spivey Sep 12 '11 at 3:28
1  
(Continued, part 2) And then I'm afraid I don't see the step from the integral to $\log(n/2) + \gamma + O(1/\sqrt{n})$ at all. (Am I missing something obvious there?) –  Mike Spivey Sep 12 '11 at 3:29
    
My concerns about your original answer still stand, but I like the new answer much better. My only question about it is in your justification of (3). Two lines after "Therefore, we choose $n$ large enough..." you have $+(1-\epsilon)$ times stuff. Didn't you just argue three lines earlier that the sum of $2^{-n} \binom{n}{k}$ is greater than $1-\epsilon$ over the interval in question rather than less than $1-\epsilon$? Still I think I believe (3) despite this concern, and I like the rest of the argument, so +1. –  Mike Spivey Sep 12 '11 at 19:34
1  
Two things: the result you need (and the one you use in the proof) is not the central limit theorem but the (strong) law of large numbers. More importantly, you apply this to the function log, which is not continuous on [0,1] (not even bounded), hence this application is not valid. –  Did Sep 12 '11 at 19:36

Here are my two proofs, in case anyone is interested.


Proof 1: The $n$th term is $\sum_{k=1}^n \frac{1}{k 2^k}$.

Let $\Delta f(k) = f(k+1) - f(k)$, i.e., the finite difference of $f(k)$.

Let $B(n) = \sum_{k=0}^n \binom{n}{k} f(k)$, $A(n) = \sum_{k=0}^n \binom{n}{k} \Delta f(k)$.

A few years ago I proved$^1$ the following relationship between $B(n)$ and $A(n)$:

$$B(n) = 2^n \left(f(0) + \sum_{k=1}^n \frac{A(k-1)}{2^k}\right).$$

Now, $\Delta H_n = \frac{1}{n+1}$. And we know that

$$\sum_{k=0}^n \binom{n}{k} \frac{1}{k+1} = \frac{1}{n+1} \sum_{k=0}^n \binom{n+1}{k+1} = \frac{2^{n+1}-1}{n+1},$$ using the fact that $\binom{n}{k} \frac{n+1}{k+1} = \binom{n+1}{k+1}$.

Thus the formula above for $B(n)$ yields

$$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \sum_{k=1}^n \frac{2^k-1}{k2^k} = 2^n\left(H_n - \sum_{k=1}^n \frac{1}{k2^k}\right).$$

Rearranging, we get $$H_n - \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} H_k = \sum_{k=1}^n \frac{1}{k 2^k}.$$

Thus $$\lim_{n \to \infty} \left(H_n - \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} H_k\right) = \sum_{k=1}^{\infty} \frac{1}{k 2^k} = \log 2,$$ where the $\log 2$ is obtained, as in Srivatsan's second answer, by substituting $-1/2$ into the Maclaurin series for $\log(1+x)$.

(This is how I first came across the limit result; I was trying to find an expression for $\sum_{k=0}^n \binom{n}{k} H_k$.)

$^1$"Combinatorial Sums and Finite Differences," Discrete Mathematics, 307 (24): 3130-3146, 2007.


Proof 2: The probabilistic argument.

Let $X_1, X_2, \ldots, X_n$ be $n$ independent and identically distributed exponential random variables with rate parameter $\lambda$. The minimum of these $n$ random variables is known to have an exponential $n \lambda$ distribution. Let $X_{(k)}$ denote the $k$th smallest. Because of the memoryless property of the exponential distribution, $X_{(k+1)} - X_{(k)}$ has an exponential $(n-k) \lambda$ distribution. So $E[X_{(k+1)} - X_{(k)}] = \frac{1}{(n-k)\lambda}$. Let $Y_n = X_{(n)}$ (i.e., the largest). Thus $$E[Y_n] = \sum_{k=0}^{n-1} E[(X_{(k+1)} - X_{(k)})= \sum_{k=1}^n \frac{1}{\lambda k} = \frac{H_n}{\lambda}.$$

Now, consider $E[Y_n | Y_n > 1]$. Since $P(X_i < 1) = 1-e^{-\lambda}$, conditioning on the number of the $X_i$ with values less than $1$ yields $$E[Y_n | Y_n > 1] = 1 + \sum_{k=0}^{n-1} \binom{n}{k} \left(1 - e^{-\lambda}\right)^k \left(e^{-\lambda}\right)^{n-k} \frac{H_{n-k}}{\lambda}$$ $$= 1 + \sum_{k=1}^n \binom{n}{k} \left(1 - e^{-\lambda}\right)^{n-k} \left(e^{-\lambda}\right)^k \frac{H_k}{\lambda}.$$

But as $n \to \infty$, $E[Y_n] - E[Y_n|Y_n > 1] \to 0$, since $P(Y_n > 1) = 1 - e^{-\lambda n}$. Therefore, $$\lim_{n \to \infty} \left(\frac{H_n}{\lambda} - \sum_{k=1}^n \binom{n}{k} \left(1 - e^{-\lambda}\right)^{n-k} \left(e^{-\lambda}\right)^k \frac{H_k}{\lambda}\right) = 1.$$

Letting $\lambda = \log 2$ yields the result.

share|improve this answer
    
+1 Very systematic proofs; nice! –  Srivatsan Sep 14 '11 at 11:10

$H_{n+1} - \frac{1}{2^n} \sum_{k=1}^n \binom{n}{k} H_k \quad $ is the expected value of $(\sum_{i=j}^{n+1} 1/i)$ where $j$ is the position of a random walk started at $j=1$ and with $j$ taking $n$ steps of +0 or +1 each with probability 1/2.

The limit is the same as for the original expression with $H_n$ and is equivalent to the statement that $j$ is (with probability approaching 1 as $n$ increases) concentrated in an interval of length $o(n)$ around $n/2$. This is much weaker than the Central Limit Theorem and would hold for fairly general random walks with average speed +1/2.

share|improve this answer
    
This is interesting, but I'm afraid I don't follow some of the points you are making. I don't see why $H_{n+1} - \frac{1}{2^n} \sum_{k=1}^n \binom{n}{k} H_k$ is the expected value of the sum expression you give. And what is $j$? It looks like an index on the sum, but then the statement "$j$ takes $n$ steps of +1 or +2..." doesn't make sense to me. I see why the limit would be the same, but exactly why is it equivalent to the statement that "$j$ [again, what is $j$?] is ... concentrated in an interval of length $o(n)$ around $n/2$"? –  Mike Spivey Sep 11 '11 at 22:27
    
To get a finite (i.e., bounded below by a positive number independent of $n$) deviation of the sum from the expected value, $j$ has to differ from $n/2$ by an amount comparable to $n$ (an amount greater than $Kn$ for some positive $K$ independent of $n$). Therefore, to get convergence to the limit the dispersion of $j$ around $n/2$ has to be $o(n)$, and I think this is enough. If not then certainly $o(n/ \log n)$ suffices, and both are very weak bounds. –  zyx Sep 11 '11 at 23:47
    
Also, if $j$ is the position after $n$ steps, what is $a_j$? And why is the expected value of the sum involving $a_j$ equal to $H_{n+1} - \frac{1}{2^n} \sum_{k=1}^n \binom{n}{k} H_k$? –  Mike Spivey Sep 12 '11 at 3:38
    
Sorry, $a_j$ is notation for $1/j$ (or whichever series has sums denoted by $H_n$, if $H_n$ is allowed to range over a more general class of series than the harmonic numbers) from an earlier edit-in-progress of a more elaborate analysis that I decided not to post. I'll remove $a_j$ from the answer above, but it can also be read in its current state as a correct argument for somewhat more general series $$H_n = \sum_{i=1}^{n} a_j$$ satisfying suitable growth conditions. –  zyx Sep 12 '11 at 4:46
    
To begin by the beginning, even after pondering this for a while, I fail to see on what result the first sentence of the post is based. If $(X_j)$ is a random walk and $h$ a function, to assert that, in full generality, when $n\to\infty$, $E(h(X_n))$ behaves like $h(E(X_n))$ is... well, slightly too optimistic for my taste. (In the present case, my impression is that in fact you need to compare $E(h_n(X_n))$ and $h_n(E(X_n))$ for some functions $h_n$ depending on $n$--which only makes the situation worse.) –  Did Sep 12 '11 at 7:39

Just an idea. $H_n$ measures the average number of ascents in a permutation from $S_n$. The weighted sum measures the average number of ascents in a permutation from $S_n$, after each entry is deleted with probability $1/2$.

One might estimate the weighted sum this way, but this seems difficult, and anyhow the trick should be to compare the two quantities somehow. However, deletion of entries can have unexpected consequences (consider $1,n,2,3,4,\ldots,n-1$). Maybe looking at the Robinson-Schensted correspondence would help.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.