# 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.

-
What does it mean to be "about linear"? –  Mercy Oct 4 '12 at 15:43
$2^r\ln \cfrac{2^r}{2^r-r} = -2^r\ln (1-\cfrac{r}{2^r})$ using $\ln (\cfrac 1 y)=-\ln(y)$ –  Mark Bennet Oct 4 '12 at 15:51
@Mercy: By "about linear" I mean the function is $\tilde{O}(r)$ –  Fixee Oct 4 '12 at 16:13

Since $\dfrac{2^r}{2^r-r} = 1 + \dfrac{r}{2^r-r}$ and for $x$ close to $0$, $\log(1+x) \approx x,$ for large $r$ we have $$2^r \log \dfrac{2^r}{2^r-r} \approx 2^r \frac{r}{2^r-r}= r \left(\frac{1}{1-r/2^r}\right)\approx r.$$

-

$2^r\ln \dfrac{2^r}{2^r-r}=2^r \ln {\dfrac{1}{1-\dfrac{r}{2^r}}}=-2^r \ln{}(1-\dfrac{r}{2^r})$. Then apply Taylor's series expansion $$\ln(1-x)=-\sum\limits_{n=1}^{\infty}{\dfrac{x^n}{n}}$$ to the last term (for sufficiently large $r$).

-

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

-