<s>[INST] Approximation for $2^r\ln \frac{2^r}{2^r-r}$ I know the function
$$2^r\ln \frac{2^r}{2^r-r}$$
is about linear in $r$, but I need an argument that an undergraduate could follow.  Is there a simple way to explain this?  I'd be happy with a simple upper-bound.
 [/INST] Consider the function $f(\theta) = -\log(1-\theta)$. If we take $|\theta| < \frac{1}{2}$, the power series expansion of $f$ is given by $f(\theta) = \theta + \sum_{k=2}^\infty \frac{\theta^k}{k}$, from which we can derive the estimate $|f(\theta) - \theta| \leq K |\theta|^2$, for some constant $K$.
Let $x>2$, then this gives $|f(\frac{1}{x}) - \frac{1}{x}| \leq K \frac{1}{x^2}$, from which we obtain $|x f(\frac{1}{x}) - 1| \leq K \frac{1}{x}$.
Now note that $\frac{2^r}{r} \log(\frac{2^r}{2^r-r}) = \frac{2^r}{r} \log(\frac{1}{1-\frac{1}{2^r/r}}) = -\frac{2^r}{r} \log(1-\frac{1}{2^r/r}) =\frac{2^r}{r} f(\frac{r}{2^r})$. Using the above estimate, we get:
$$|\frac{2^r}{r} \log(\frac{2^r}{2^r-r})-1| \leq K \frac{r}{2^r}$$
which is valid when $2^r > 2 r$. Multiplying through by $r$ gives
$$|2^r \log(\frac{2^r}{2^r-r})-r| \leq K \frac{r^2}{2^r},$$
which shows that $2^r \log(\frac{2^r}{2^r-r})$ is arbitrarily close to $r$ for large values of $r$.
</s>