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.

 A: 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).
$$

A: hint: prove LHS$<\dfrac{2^n}{n}(2+\dfrac{6}{n})$ when $n\ge3$
A: The inequality $\sum_{k=1}^n 2^k/k \lt 3\cdot2^n/n$ can be proved by verifying it for $n=1$, $2$ and $3$ and then using the inequality
$${3\over n}\le{4\over n+1}\text{ for } n\ge3$$
in an inductive step:
$$\begin{align}
\sum_{k=1}^{n+1}{2^k\over k} &= \sum_{k=1}^n{2^k\over k}+{2^{n+1}\over n+1}\cr
&\lt 3{2^n\over n}+{2^{n+1}\over n+1}\cr
&\le {4\over n+1}2^n +{2^{n+1}\over n+1}\cr
&=2{2^{n+1}\over n+1}+{2^{n+1}\over n+1}\cr
&=3{2^{n+1}\over n+1}\cr
\end{align}$$
The limit for $(n/2^n)\sum_{k=1}^n(2^k/k)$ can be determined by writing the sum as
$$\sum_{k=1}^n{n\over k}{1\over2^{n-k}}=\sum_{m=0}^{n-1}{n\over n-m}{1\over2^m}=\sum_{m=0}^{n-1}\left(1+{m\over n-m}\right){1\over2^m}=\sum_{m=0}^{n-1}{1\over2^m}+\sum_{m=0}^{n-1}{m\over n-m}{1\over2^m}$$
Now the first sum we wind up with is
$$\sum_{m=0}^{n-1}{1\over2^m}=1+{1\over2}+{1\over4}+\cdots+{1\over2^{n-1}}=2-{1\over2^{n-1}}$$
which clearly has limit $2$ as $n\rightarrow\infty$.  So it remains to show that the second sum,
$$\sum_{m=0}^{n-1}{m\over n-m}{1\over2^m}={0\over1\cdot n}+{1\over2(n-1)}+{2\over4(n-2)}+{3\over8(n-3)}+\cdots+{n-1\over2^{n-1}\cdot1}$$
tends to $0$ as $n$ tends to $\infty$.  This can be done using rather crude estimates, provided we split the sum into two pieces: the "early" terms where $m/(n-m)$ is small and the "late" pieces where $1/2^m$ is small.  A convenient place for the split is at around $m=\sqrt[3]n$.  If we do, then the "early" terms are all less than $\sqrt[3]n/(n-\sqrt[3]n)\approx n^{-2/3}$ so that piece is less than $n^{-1/3}$, which tends to $0$, while the "late" terms are all less than $n/2^{n^{1/3}}$, so that piece is less than $n^2/2^{n^{1/3}}$, which also tends to $0$.  (It might be convenient here to write $n=x^3$, so that we're looking at the limit $x^6/2^x$ as $x\rightarrow\infty$.  The point is, the exponential dominates any polynomial in the limit.)
A: I will answer myself the second question (which is actually more important).
Write it as $$\lim_{n\rightarrow\infty}\sum_{k=1}^n\frac{n}{k}\frac{1}{2^{n-k}}=2$$. We can split the sum at index $a_n$.
$$\sum_{k=1}^{a_n-1}\frac{n}{k}\frac{1}{2^{n-k}}\le\sum_{k=1}^{a_n-1}\frac{n}{1}\frac{1}{2^{n-k}}=n(\frac{1}{2^{n-a_n}}-\frac{1}{2^{n-1}})\le\frac{n}{2^{n-a_n}}$$
On the other hand, $$\sum_{k=a_n}^{n}\frac{n}{k}\frac{1}{2^{n-k}}\le\sum_{k=a_n}^{n}\frac{n}{a_n}\frac{1}{2^{n-k}}\le2\frac{n}{a_n}$$.
It is now clear that we only need to choose $a_n$ such that $\displaystyle\frac{n}{a_n}\rightarrow 1$ but $2^{n-a_n}$ is meanwhile big enough to eliminate $n$. We have a lot of choices, for example, $a_n=[n-\sqrt{n}]$.
