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} $
Best Answer
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.