<s>[INST] How to prove $\sum_{k=1}^n \frac{2^k}{k}< 3\frac{2^n}{n}$? How to prove $$\sum_{k=1}^n \frac{2^k}{k}< 3\frac{2^n}{n}$$ and further $$\lim_{n\rightarrow \infty}\frac{n}{2^n}\sum_{k=1}^n 
\frac{2^{k}}{k} = 2$$?
These results are verified by computer, yet I can't figure out a neat proof.

 [/INST] I'll answer the second part of the question.  It is helpful to notice that the sum
$$
S_n = \sum_{k=1}^n \frac{2^k}{k}
$$
is dominated by only a few terms near $k=n$.  In a sense, the terms near the end constitute the principal contribution to the whole sum, while the terms near the beginning are negligible.  We can therefore hope for a good estimate for the whole sum by splitting it apart into these two pieces and estimating them individually.
In this case it turns out that we can split the sum evenly.
For the first half we can get away with the crude estimate
$$
\begin{align}
\sum_{k=1}^{\lfloor n/2 \rfloor} \frac{2^k}{k} &< \sum_{k=1}^{\lfloor n/2 \rfloor} 2^k \\
&= 2\left(2^{\lfloor n/2 \rfloor}-1\right) \\
&< 2^{n/2+1} \\
&= O\left(2^{n/2}\right).
\end{align} \tag{1}
$$
To help us estimate the second half of the sum we will introduce the new variable $h=n-k$.  Note that when $\lfloor n/2 \rfloor + 1 \leq k \leq n$ we have $0 \leq h < n/2$.
The power series for $1/(1-x)$ converges uniformly and absolutely on the interval $[0,1/2]$, so we can write $1/(1-x) = 1 + O(x)$ there.  We then have
$$
\begin{align}
\frac{1}{k} &= \frac{1}{n-h} \\
&= \frac{1}{n} \cdot \frac{1}{1-h/n} \\
&= \frac{1}{n} \left[1 + O\left(\frac{h}{n}\right)\right] \\
&= \frac{1}{n} + O\left(\frac{h}{n^2}\right)
\end{align} \tag{$\star$}
$$
for $n \geq 1$ and $\lfloor n/2 \rfloor + 1 \leq k \leq n$.  This allows us to rewrite the second half of $S_n$ as
$$
\sum_{k=\lfloor n/2 \rfloor + 1}^{n} \frac{2^k}{k} = \frac{1}{n} \sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^k + \sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^k O\left(\frac{h}{n^2}\right). \tag{2}
$$
The first sum on the right-hand side is
$$
\begin{align}
\sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^k &= 2^{\lfloor n/2 \rfloor + 1} \sum_{k=0}^{\lceil n/2 \rceil - 1} 2^k \\
&= 2^{\lfloor n/2 \rfloor + 1} \left(2^{\lceil n/2 \rceil}-1\right) \\
&= 2^{n+1} + O\left(2^{n/2}\right),
\end{align}
$$
where we have used the fact that $\lfloor n/2 \rfloor + \lceil n/2 \rceil = n$.  To estimate the second sum we first rewrite it in terms of $h$ and $n$ only:
$$
\begin{align}
\frac{1}{n^2} \sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^k h &= \frac{2^n}{n^2} \sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^{k-n} h \\
&= \frac{2^n}{n^2} \sum_{h=0}^{\lceil n/2 \rceil - 1} 2^{-h}h.
\end{align}
$$
The quantity $\sum_{h=0}^{\lceil n/2 \rceil - 1} 2^{-h}h$ is bounded, so for the second sum we get the estimate
$$
\sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^k O\left(\frac{h}{n^2}\right) = O\left(\frac{2^n}{n^2}\right).
$$
Combining these and absorbing the first error term into the second we find that $(2)$ becomes
$$
\begin{align}
\sum_{k=\lfloor n/2 \rfloor + 1}^{n} \frac{2^k}{k} &= \frac{2^{n+1}}{n} + O\left(\frac{2^{n/2}}{n}\right) + O\left(\frac{2^n}{n^2}\right) \\
&= \frac{2^{n+1}}{n} + O\left(\frac{2^n}{n^2}\right).
\end{align}
$$
By using the estimate in $(1)$ we obtain an estimate for the whole sum,
$$
\begin{align}
S_n &= \sum_{k=1}^{\lfloor n/2 \rfloor} \frac{2^k}{k} + \sum_{k=\lfloor n/2 \rfloor + 1}^{n} \frac{2^k}{k} \\
&= O\left(2^{n/2}\right) + \frac{2^{n+1}}{n} + O\left(\frac{2^n}{n^2}\right) \\
&= \frac{2^{n+1}}{n} + O\left(\frac{2^n}{n^2}\right).
\end{align}
$$
Thus

$$
\frac{n}{2^n} \sum_{k=1}^{n} \frac{2^k}{k} = 2 + O\left(\frac{1}{n}\right).
$$

If you desire more terms in the approximation you can take more terms in the series expansion $(\star)$.  For instance, taking
$$
\frac{1}{k} = \frac{1}{n} + \frac{h}{n^2} + O\left(\frac{h^2}{n^3}\right)
$$
yields

$$
\frac{n}{2^n} \sum_{k=1}^{n} \frac{2^k}{k} = 2 + \frac{2}{n} + O\left(\frac{1}{n^2}\right).
$$

</s>