Expected empirical entropy I'm thinking about some properties of the empirical entropy for binary strings of length $n$ when the following question crosses my way:

$\underbrace{\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize nH_{0}(w)}_{\large\#}\;\overset{?}{=}\;n-\varepsilon_{n}\;\;\;$
with $\;\;\lim\limits_{n\rightarrow\infty}\varepsilon_{n}=c\;\;\;$ and $\;\;\;\forall n:\;\varepsilon_{n}&gt;0$
where $c$ is a constant.
Is that equation true? For which function $\varepsilon_{n}$ respectively which constant $c$?
$ $
$n=2\;\;\;\;\;\;\;\rightarrow\;\#=1 $
$n=3\;\;\;\;\;\;\;\rightarrow\;\#\approx 2.066 $
$n=6\;\;\;\;\;\;\;\rightarrow\;\#\approx 5.189 $
$n=100\;\;\;\rightarrow\;\#\approx 99.275 $
$n=5000\;\rightarrow\;\#\approx 4999.278580 $
$n=6000\;\rightarrow\;\#\approx 5999.278592 $

$ $
Backround
$ $
$H_{0}(w)$ is the zeroth-order empircal entropy for strings over $\Sigma=\left\{0,1\right\}$:

$H_{0}(w)=\frac{|w|_{0}}{n}\log\frac{n}{|w|_{0}}+\frac{n-|w|_{0}}{n}\log\frac{n}{n-|w|_{0}}$

where $|w|_{0}$ is the number of occurences of $0$ in $w\in\Sigma^{n}$.
The term $nH_{0}(w)$ corresponds to the Shannon-entropy of the empirical distribution of binary words  with respect to the number of occurences of $0$ respectively $1$ in $w\in\Sigma^{n}$.
More precise:
Let the words in $\left\{0,1\right\}^{n}$ be possible outcomes of a Bernoulli process. If the probability of $0$ is equal to the relative frequency of $0$ in a word $w\in\left\{0,1\right\}^{n}$, then the Shannon-entropy of this Bernoulli process is equal to $nH_{0}(w)$.
At this point, my question should be more reasonable since the first term normalizes the Shannon-entropies for all empirical distributions of words $w\in\left\{0,1\right\}^{n}$.
Intuitively I thought about getting something close to the Shannon-entropy of the uniform distribution of $\left\{0,1\right\}^{n}$, which is $n$.
By computing and observing some values I've got the conjecture above, but I'm not able to prove it or to get the exact term $\varepsilon_{n}$.
It is easy to get the following equalities:
$\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize nH_{0}(w)\;\;=\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize |w|_{0}\log\frac{n}{|w|_{0}}+(n-|w|_{0})\log\frac{n}{n-|w|_{0}}$
$=\large\frac{1}{2^{n}}\normalsize\sum\limits_{k=1}^{n-1}$ $n\choose k$ $\left(k\log\frac{n}{k}+(n-k)\log\frac{n}{n-k}\right)$
and it is possible to apply some logarithmic identities but I'm still in a dead point.
(the words $0^{n}$ and $1^{n}$ are ignored, because the Shannon-entropy of their empirical distributions is zero)
Any help is welcome.
Here is another approach, based on information theory and heavily inspired by @usul's answer. It shows that $\epsilon_n=O(1)$ with very few calculations, and can be used to prove that $\epsilon_n \rightarrow \log_2 \sqrt{e}$ and to derive good estimates on the rate of convergence with less calculations than @usul's approach. In fact, I find a closed-form expression for $\epsilon_n$ : $$(1)  \; \; \; \; \epsilon_n = n \left( H(Binom(n,1/2)) - H \left( Binom \left( n-1, 1/2 \right) \right) \right) \ .$$

Details:

Let $X$ be a uniform random variable in $\{0,1\}^n$. Let $K$ be a random variable equal to the number of 1's in $X$. The expression $\#$ that @Danny wants to analyze is exactly equal to $n \cdot \mathbb{E}_{k} [H(X_1 | K=k)]$. (Here $X_1$ is the first bit of $X$.) By the basic properties of the entropy operator,
$$(2)  \; \; \; \; \# = n\mathbb{E}_{k} [H(X_1 | K=k)]=nH(X_1|K)=n(H(X_1K)-H(K))=n(H(K|X_1)+H(X_1)-H(K)) = n(1-H(Binom(n,1/2)) + H(Binom(n-1,1/2))) \ .$$
The last equality follows from the fact that $X_1$ is just a uniformly random bit, $K$ is the binomial distribution, and $K|(X_1=x_1)$ is distributed either as $Binom(n-1,1/2)$ or as $Binom(n-1,1/2)+1$, depending on the value of $x_1$, both of which have the same entropy.

This already gave us equation (1). Now we just need to calculate to get the value of $\lim_{n \rightarrow \infty} \epsilon_n$

We use any known estimation for the entropy of a binomial RV, such as here. We see that $$ (3)  \; \; \; \; H(K)=H(Binom(n,1/2))=\frac12 \log_2 ( \pi en / 2) + O(1/n) \ ,$$ and, similarly, that $$H(K|X_1)=H(Binom(n-1,1/2))=\frac12 \log_2 ( \pi e(n-1)/2) + O(1/n) \ .$$ Canceling out terms and substituting into (1), we get $$ (4)  \; \; \; \; \epsilon_n = n \cdot (H(K)-H(K|X_1)) = n \cdot \frac12 (\log_2 (n/(n-1)) + O(1/n)) = \\ \frac12 \log_2 ((n/(n-1))^n) + O(1) \rightarrow \log_2(\sqrt{e}) + O(1) \ . $$

By slightly improving the approximation (3) we should be able to replace the $O(1)$ term in (4) by $O(1/n)$ and therefore get that, indeed, $\lim_{n \rightarrow \infty} \epsilon_n = \log_2 \sqrt{e}$. To get this better estimation it should be enough to check that $H(Binom(n,1/2))=\frac12 \log_2 ( \pi en / 2) + err(n)$ where $err(n)=O(1/n)$ and $err$ is a monotone function.