Prove by induction on n that $\sum\limits_{k=1}^n \frac {2^{k}}{k} \leq 2^{n}$

Question

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} $

Answer 1

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.

Answer 2

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$$

Answer 3

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.