Proofs of $\lim\limits_{n \to \infty} \left(H_n - 2^{-n} \sum\limits_{k=1}^n \binom{n}{k} H_k\right) = \log 2$ 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$.) 

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).
$$
