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