Induction with inequality problem

Question

Prove by induction that $2k(k+1) + 1 < 2^{k+1} - 1$ for $ k > 4$. Can some one pls help me with this?

I reformulated like this

$ 2k(k+1) + 1 < 2^{k+1} - 1 $

$ 2k^2+2k+2<2^{k+1}$

and I tried like this Take $k=k+1$

$ 2^{k+2} -1 > 2(k+1)(k+2) + 1 $

$2^{k+2} > 2(k+1)(k+2) + 2$

$ 2^{k+2} > 2k^2+2k+2 +4k+4$

I dont know how to proceed further

Please help me.

score 1 · Answer 1 · answered Sep 30 '13 at 17:00

1

You want to show $2k(k+1)+2<2^{k+1}$

For this, $k=5$ holds true (why?)

Further, $2^{k+2} = 2\cdot 2^{k+1} > 2\cdot(2k^2+2k+2) = 4k^2 + 4k + 4 = (2k^2 + 6k + 6)+2(k^2-k-1) $

Now can you recognise the first part in brackets and show that the second part is positive for $k> 4$?

answered Sep 30 '13 at 17:00

Macavity

why do I need to that part is positive.I am not clear and how to show that . – Proton Boss Sep 30 '13 at 17:08
Pls help me . i still dint solve it. – Proton Boss Sep 30 '13 at 17:28
Exactly where are you having trouble? – Macavity Sep 30 '13 at 17:29

score 1 · Answer 2 · answered Sep 30 '13 at 22:23

I'll continue from you have started:

$$2k(k+1) + 1 < 2^{k+1} - 1$$ $$2k^2 + 2k + 2 < 2^{k+1}$$

Divide both side by 2:

$$k^2 + k + 1< 2^k$$

Obviously $k^2 > k$ and $2>1$, so we can transform the inequality to:

$$2k^2 + 2 < 2^k$$ $$k^2 + 1 < 2^k$$

And for the base case $k=5$ it's true, so it's true for every $k\ge 5$, because the RHS grow exponentialy, while the LHS is polynomial.

2 Answers2