Computing $\lim_n \frac{n}{2^n}\sum_{k=1}^n \frac{2^k}{k}$ 
What is $\lim_n \frac{n}{2^n}\sum_{k=1}^n \frac{2^k}{k}$ ?

Here are a few remarks:


*

*Since $x\mapsto \frac{2^x}{x}$ is increasing when $x\geq 2$, one might be tempted to use the integral test. This fails: when doing so, one gets $a_n\leq \sum_{k=1}^n \frac{2^k}{k}\leq b_n$ where $a_n\sim \frac{2^n}{\ln (2)n}$ and $b_n\sim \frac{2^{n+1}}{\ln (2)n}$. 
Unfortunately $b_n$ is too big and this estimate doesn't yield the limit.

*Here's my solution: since it's easy to sum $2^k$ and the difference $\frac{1}{k}-\frac{1}{k+1}$ is small, it's natural to try summation by parts: $$\begin{align} \sum_{k=1}^n \frac{2^k}{k}
&=\frac{S_n}{n+1}-1+\sum_{k=1}^n S_k \left(\frac{1}{k}-\frac{1}{k+1} \right)\quad \text{where} \; S_n=\sum_{k=0}^n 2^k\\
&= \frac{2^{n+1}}{n+1} + \sum_{k=1}^n \frac{2^{k+1}}{k(k+1)} - \underbrace{1 - \sum_{k=1}^n\left(\frac{1}{k(k+1)}\right) - \frac{1}{n+1}}_{\text{bounded}}\\
\end{align}$$
Intuition suggests $\displaystyle \sum_{k=1}^n \frac{2^{k+1}}{k(k+1)}=o\left(\frac{2^n}n \right)$ but it's not immediate to prove. I had to resort to another summation by parts! Indeed 
$$\begin{align}\small\sum_{k=1}^n \frac{2^{k+1}}{k(k+1)}&= \small 2\left[ \frac{2^{n+1}}{n(n+1)} + 2\sum_{k=1}^n \left(\frac{2^{k+1}}{k(k+1)(k+2)}\right)-\frac 12 -2\sum_{k=1}^n \left(\frac{1}{k(k+1)(k+2)}\right) - \frac{1}{n(n+1)}\right]\\
 &\small\leq \frac{2^{n+2}}{n(n+1)}+\frac{2^{n+2}}{n(n+1)(n+2)}\cdot n \\
&\small= o\left(\frac{2^n}n \right)
\end{align}$$
Hence $$\sum_{k=1}^n \frac{2^k}{k} = \frac{2^{n+1}}{n+1} + o\left(\frac{2^n}n \right)$$ and $$\lim_n \frac{n}{2^n}\sum_{k=1}^n \frac{2^k}{k} = 2$$


This solution is quite tedious and computational... That's why I'm looking for a shorter or smarter solution that avoids summation by parts (integration by parts is easy to perform on functions, it just gets quite heavy with series).

 A: Let $S_n = \frac{n}{2^n} \sum_{k=1}^{n} \frac{2^k}{k}$. It has the following trivial lower bound.
$$ 2 - \frac{1}{2^n} = \sum_{k=1}^{n} \frac{1}{2^{n-k}} \leq S_n. $$
For an upper bound, fix $r \in (0, 1)$ and let $N = N(r,n) = \lfloor rn \rfloor$. Then for $n$ large, we have $1 < N < n$ and hence
\begin{align*}
S_n
&= \frac{n}{2^n} \sum_{k=1}^{N} \color{red}{\frac{2^k}{k}} + \frac{n}{2^n} \sum_{k=N+1}^{n} \color{blue}{\frac{2^k}{k}} \\
&\leq \frac{n}{2^n} \sum_{k=1}^{N} \color{red}{2^k}+ \frac{n}{2^n} \sum_{k=N+1}^{n} \color{blue}{\frac{2^k}{rn}} \\
&= \frac{n}{2^n} (2^{N+1} - 1) + \frac{1}{r 2^n}(2^{n+1} - 2^{N+1}) \\
&\leq n 2^{-(1-r)n+1} + \frac{2}{r}.
\end{align*}
For the red terms, we utilized the trivial bound $\frac{1}{k} \leq 1$. For the blue terms, we utilized the fact that $k \geq N+1$ implies $k \geq nr$. Thus it follows that
$$ 2 \leq \liminf_{n\to\infty} S_n \leq \limsup_{n\to\infty} S_n \leq \frac{2}{r}. $$
Taking $r \uparrow 1$ gives the wanted conclusion.
A: $\begin{array}\\
\frac{n}{2^n}\sum_{k=1}^n \frac{2^k}{k}
&=n\sum_{k=1}^n \frac{2^{k-n}}{k}\\
&=n\sum_{k=0}^{n-1} \frac{2^{-k}}{n-k}\\
&=\sum_{k=0}^{n-1} \frac{2^{-k}}{1-k/n}\\
\text{so}\\
\frac{n}{2^n}\sum_{k=1}^n \frac{2^k}{k}-2
&=\sum_{k=0}^{n-1} 2^{-k}(\frac1{1-k/n}-1)-\frac1{2^{n-1}}\\
&=\sum_{k=0}^{n-1} 2^{-k}(\frac{k/n}{1-k/n})-\frac1{2^{n-1}}\\
\end{array}
$
If $k \le cn$,
$2^{-k}(\frac{k/n}{1-k/n})
\le 2^{-k}\frac{c}{1-c}
$
so
$\sum_{k=0}^{\lfloor nc \rfloor} 2^{-k}(\frac{k/n}{1-k/n})
\le 2\frac{c}{1-c}
\lt 4c$
if
$0 < c < \frac12$.
If
$k > cn$,
$\begin{array}\\
\sum_{k=cn}^{n-1} 2^{-k}(\frac{k/n}{1-k/n})
&<\sum_{k=cn}^{n-1} 2^{-cn}(\frac{k/n}{1-k/n})\\
&=2^{-cn}\sum_{k=cn}^{n-1} (\frac{k}{n-k})\\
&<2^{-cn}\sum_{k=cn}^{n-1} n\\
&<n^22^{-cn}\\
&<e^{-cn \ln 2 + 2\ln n}\\
\end{array}
$
For any fixed $c > 0$,
$-cn \ln 2 + 2\ln n
\to -\infty$
as
$n \to \infty$,
so that
$e^{-cn \ln 2 + 2\ln n}
\to 0$.
By first choosing $c$ small
and then $n$ large,
both
$4c$ and
$e^{-cn \ln 2 + 2\ln n}$
can be made as small as we want,
so that
$\frac{n}{2^n}\sum_{k=1}^n \frac{2^k}{k}-2
$
can be made as small as we want,
so that
$\lim_{n \to \infty}\frac{n}{2^n}\sum_{k=1}^n \frac{2^k}{k}
=2
$.
A: Let
$$ S_n=\frac{n}{2^n}\sum_{k=1}^n\frac{2^k}{k}. \tag{1}$$
Clearly
$$ S_n=\sum_{k=1}^n\frac{n}{k}\frac1{2^{n-k}}\ge \sum_{k=1}^n\frac1{2^{n-k}}=2-\frac{1}{2^n}. $$
Define
\begin{eqnarray}
f_n(x)=\frac{n}{2^n}\sum_{k=1}^n\frac{2^k}{k}\left(\frac12x\right)^k
\end{eqnarray}
and then $f_n(0)=0,f_n(2)=S_n$ and
$$ f_n'(x)=\frac{n}{2^n}\sum_{k=1}^nx^{k-1}=\frac{n}{2^n}\frac{1-x^n}{1-x}.$$
So
\begin{eqnarray}
S_n&=&\frac{n}{2^n}\int_0^2\frac{1-x^n}{1-x}dx\\
&=&\frac{n}{2^n}\int_0^1\frac{1-x^n}{1-x}dx+\frac{n}{2^n}\int_1^2\frac{x^n-1}{x-1}dx.
\end{eqnarray}
Since
$$ \int_0^1\frac{1-x^n}{1-x}dx=\ln n+\gamma+o(1),$$
one 
$$ \frac{n}{2^n}\int_0^1\frac{1-x^n}{1-x}dx=o(1). $$
Noting that if $x\in[1,2]$, then $x-1\ge1$ and $x^n-1\le x^n$, one has
$$ S_n\le o(1)+\frac{n}{2^n}\int_1^2\frac{x^n-1}{x-1}dx\le o(1)+\frac{n}{2^n}\int_1^2x^ndx=o(1)+\frac{n}{2^n}\frac{1}{n+1}(2^{n+1}-1).\tag{2}$$
From (1) and (2), one has
$$ 2-\frac{1}{2^n}\le S_n\le o(1)+\frac{n}{2^n}\frac{1}{n+1}(2^{n+1}-1).$$
Letting $n\to\infty$, one has
$$ \lim_{n\to\infty}S_n=2. $$
A: Let $f(x)=\sum_{k=1}^n\frac{x^k}{k}$.  Then, we can write
$$f(x)=\sum_{k=1}^n \int_0^x t^{k-1}\,dk=\int_0^x \frac{1-t^n}{1-t}\,dt$$
so that $f(2)=\sum_{k=1}^n\frac{2^k}{k}=\int_0^2 \frac{1-t^n}{1-t}\,dt$.

Next, we choose $0<\delta<1$ and write
$$\begin{align}
\frac{n}{2^n}\int_0^2 \frac{1-t^n}{1-t}\,dt&=\frac{n}{2^n}\int_0^{2-\delta}\frac{1-t^n}{1-t}\,dt+\frac{n}{2^n}\int_{2-\delta}^2\frac{t^n-1}{t-1}\,dt \tag 1
\end{align}$$
We can apply the mean-value theorem for the second term on the right-hand side of $(1)$ to reveal that for some $\xi_n\in [2-\delta,2]$ 
$$\begin{align}
\frac{n}{2^n}\int_{2-\delta}^2 \frac{t^n-1}{t-1}\,dt&=\frac{n}{2^n(\xi_n-1)}\int_{2-\delta}^2(t^n-1)\,dt\\\\
&=\frac{n}{2^n(\xi-1)}\left(\frac{2^{n+1}-(2-\delta)^{n+1}}{n+1}+\delta\right) \tag 2
\end{align}$$
Letting $n\to \infty$ in $(2)$ yields
$$\lim_{n\to \infty}\frac{n}{2^n}\int_{2-\delta}^2 \frac{t^n-1}{t-1}\,dt=\frac{2}{\xi-1}$$
For any given $\epsilon>0$, we can choose $0<\delta<1$ so small that $\left|\frac{2}{\xi_n-1}-2\right|<\epsilon$.  Now, we proceed with that $0<\delta<1$ fixed.  
Noting that $\frac{1-t^n}{1-t}$ is positive and monotonically increasing on $[0,2]$, the first term on the right-hand side of $(1)$ is bounded above by $\frac{n}{2^n}\frac{(2-\delta)^n-1}{1-\delta}\to 0$ as $n\to \infty$.

Putting it all together, we obtain the coveted limit

$$\lim_{n\to \infty}\frac{n}{2^n}\sum_{k=1}^n\frac{2^k}{k}=2$$

A: I encountered this limit when computing
$$
\sum_{k=0}^n\frac1{\binom{n}{k}}=\frac{n+1}{2^n}\sum_{k=0}^n\frac{2^k}{k+1}
$$
in equation $(8)$ of this answer, and for which an asymptotic expansion is given in equation $(6)$ of this answer:
$$
\begin{align}
\frac{n}{2^n}\sum_{k=1}^n\frac{2^k}k
&=\sum_{k=1}^n\frac1{\binom{n-1}{k-1}}\\
&\sim2+\frac2{n-1}+\frac4{(n-1)(n-2)}+\frac{12}{(n-1)(n-2)(n-3)}\\
&+\frac{48}{(n-1)(n-2)(n-3)(n-4)}+O\left(\frac1{n^5}\right)
\end{align}
$$
A: Write the expression as
$$\frac{\sum_{k=1}^{n}2^k/k}{2^n/n}.$$
Note the denominator $\to \infty.$ That rings the Stolz-Cesaro bell, so consider
$$\frac{2^{n+1}/(n+1)}{2^{n+1}/(n+1) -2^n/n} = \frac{1}{1 -(n+1)/(2n)} \to \frac{1}{1/2} = 2.$$
By Stolz-Cesaro, the desired limit is $2.$
