Prove by induction on n that $\sum\limits_{k=1}^n \frac {2^{k}}{k} \leq 2^{n}$ I am at a beginners level so I'm not sure if this is correct.
So here is what I did,
Base Case:
for n = 1
LHS: $\frac {2^{1}}{1} = 2$ 
RHS: $2^{1} = 1$
So LHS = RHS
Inductive Case:
for n+1
$\sum\limits_{k=1}^{n+1} \frac {2^{k}}{k} \ + \ \frac {2^{n+1}} {n+1}$
Then inductive hypothesis
$\sum\limits_{k=1}^{n+1} \ 2^{n}\ + \ \frac {2^{n+1}} {n+1}$
Now this is where I got stuck, from  here can I take the summation of both sides of the sign separately and for $\sum\limits_{k=1}^{n+1}  \frac {2^{n+1}} {n+1}$ can I multiply by n+1 take the summation and then divide by (n+1) at the end?
Is this the correct way to solve?
Also I'm not sure how $\sum\limits_{k=1}^{n+1}$ will effect my answer vs $\sum\limits_{k=1}^{n} $
 A: You have to be a little more careful with the expressions you are writing down. 
After showing the base case, you should assume $\displaystyle\sum_{k = 1}^{n}\dfrac{2^k}{k} \le 2^n$ and prove $\displaystyle\sum_{k = 1}^{n+1}\dfrac{2^k}{k} \le 2^{n+1}$. 
So your first steps to proving that inequality should be something like $$\displaystyle\sum_{k = 1}^{n+1}\dfrac{2^k}{k}  = \dfrac{2^{n+1}}{n+1}+\sum_{k = 1}^{n}\dfrac{2^k}{k} \le \dfrac{2^{n+1}}{n+1}+2^n \le \cdots$$
A: Base case: Assume that for some $x$ the sum
$$\sum_{k=1}^x \frac {2^{k}}{k} \leq 2^{x}$$
Then adding the next term
$$\sum_{k=1}^{x+1} \frac {2^{k}}{k} \leq 2^{x}+\frac{2^{x+1}}{x+1}=2^x(1+\frac2{x+1})$$
Now as $\frac2{x+1}\lt1$ for $x\gt2$ we can say that
$$\sum_{k=1}^{x+1} \frac {2^{k}}{k} \leq2^x(1+1)\le2^{x+1}$$
Thus if it is true for some $x$ it is also true for $x+1$. Testing $x=1,2$ individually we see that
$$\sum_{k=1}^{1} \frac {2^{k}}{k} \le2$$
$$\sum_{k=1}^{2} \frac {2^{k}}{k} \le2^2$$
and so the summation is always less than $2^n$ by induction.
A: Here is the induction step.
$$\sum_{k=1}^{n+1} {2^k\over k} = {2^{n+1}\over n+1} + \sum_{k=1}^n {2^k\over k}. $$
Since $n\ge 1$, 
$${2^{n+1}\over n+1} \le 2^n. $$
You are now done.
