<s>[INST] Asymptotic behavior of $\sum\limits_{k=1}^n \frac{2^k}{k}$ I'm looking for an asymptotic equivalent of
$$\sum_{0 < k \le n} \frac{2^k}{k}$$
as $n \to \infty$. A plausible candidate seems to be $\frac{2^{n+1}}{n+1}$ (WolframAlpha plot, and the intuitive similarity with $\sum_{k \le n} 2^k = 2^{n+1}$ is also appealing), but my usual tricks seem powerless here.
I've tried:


*

*Interpreting $x^k/k$ as the primitive of $x^{k-1}$ and setting $x=2$

*Replacing $2^k/k$ with $\int_{x=0}^2 x^{k-1}$

*Reordering the sum's terms to expose log-resembling sub-sums like $\sum_k 1/k$

*Finding lower and upper bounds asymptotically equivalent to $\frac{2^{n+1}}{n+1}$ -- the lower bound is easy ($\sum\limits_{k \le n}  \frac{2^k}{k} \ge \sum\limits_{k \le n} \frac{2^k}{n+1} \ge \frac{\sum\limits_{k \le n} 2^k}{n+1} \ge \frac{2^{n+1}}{n+1}$), but the upper bound seems trickier (I couldn't think of a sequence $\varepsilon_k \in o(2^k/k)$ that would make it easy to estimate $\sum_{0 < k \le n} 2^k/k - \varepsilon_k$)

*... and a few others, to no avail


Any hints?
 [/INST] The Euler-Maclaurin summation formula is useful for approximating sums and often reveals the asymptotic behavior with only a few terms.  This problem is an interesting application because the precise asymptotic behavior requires summing an infinite number of terms with Bernoulli numbers as coefficients  - the terms that are typically neglected. 
Using the Euler-Maclaurin summation formula with $f(x) = 2^x/x$ 
$$\sum_{k=1}^{n}\frac{2^k}{k} = C+\int_{1}^{n}f(x)\,dx + \frac1{2}f(n)+\frac{B_2}{2!}f'(n) + \frac{B_4}{4!}f'''(n)+ \ldots.$$
The integral is the exponential integral which behaves asymptotically as $Ei(x) \sim e^x/x$ as $x \rightarrow \infty:$
$$\int_{1}^{n}f(x)\,dx=\int_{1}^{n}\frac{2^x}{x}\,dx= Ei(n\log2)-Ei(\log2) \sim \frac{e^{n\log 2}}{n\log 2}.$$
Taking the odd-order derivatives we find a pattern
$$f'(x) = \frac{2^x}{x}\left(\log2-\frac1{x}\right)\sim\frac{2^x}{x}\log2\\
f'''(x) = \frac{2^x}{x}\left[\left(\log2-\frac1{x}\right)^3+O(x^{-2})\right]\sim\frac{2^x}{x}(\log 2)^3\\ \ldots$$
Hence,
$$\sum_{k=1}^{n}\frac{2^k}{k} \sim \frac{2^n}{n}\left[\frac1{\log 2}+\frac1{2}+\frac1{\log 2}\left(\frac{B_2}{2!}(\log 2)^2 + \frac{B_4}{4!}(\log 2)^4+ \ldots\right)\right]\,\,(*)$$
The trailing terms can be summed exactly.  The generating function for the Bernoulli numbers is $x/(e^x-1)$ where
$$\frac{x}{e^x-1} = \sum_{k=0}^{\infty}\frac{B_kx^k}{k!}.$$
The first two Bernoulli numbers are $B_0 = 1$ and $B_1 = -1/2$.  They are zero for odd $n \geq 3$.
Hence,
$$\sum_{k=2}^{\infty}\frac{B_k(\log 2)^k}{k!} = \frac{\log 2}{e^{\log 2}-1}-1 + \frac{\log 2}{2}= \log 2-1 + \frac{\log 2}{2}.$$
Substituting into $(*)$ we get
$$\sum_{k=1}^{n}\frac{2^k}{k} \sim \frac{2^n}{n}\left[\frac1{\log 2}+\frac1{2}+\frac1{\log 2}\left(\log 2-1 + \frac{\log 2}{2}\right)\right]=\frac{2^n}{n}2,$$
and
$$\sum_{k=1}^{n}\frac{2^k}{k} \sim \frac{2^{n+1}}{n}$$
</s>