# Mathematics Induction on Inequality

I want to prove

$2^n \ge 3n^2 +5$--call this statement $S(n)$--for $n\ge8$

Basis step with $n = 8$, which $\text{LHS} \ge \text{RHS}$, and $S(8)$ is true. Then I proceed to inductive step by assuming $S(k)$ is true and so

$2^k \ge 3k^2 +5$

Then $S(k+1)$ is

$2^{k+1} \ge 3(k+1)^2 + 5$

I need to prove it so I continue by

$2^{k+1} \ge 3k^2 +5$

$2(2^k) \ge 2(3k^2 +5)$

I'm stuck here...don't know how to continue, please explain to me step by step. I search for whole day already, all give answer without explanation. I can't understand, sorry for the trouble.

-

The missing step (because there is indeed a missing step) is that $2\cdot(3k^2+5)\geqslant3(k+1)^2+5$. This inequality is equivalent to $3k^2-6k+2\geqslant0$, which obviously holds for every $k\geqslant8$ since $3k^2-6k+2=3k(k-2)+2$, hence you are done.

The structure of the proof that $S(k)$ implies $S(k+1)$ for every $k\geqslant8$ is as follows:

• Assume that $S(k)$ holds, that is, $2^k\geqslant3k^2+5$, and that $k\geqslant8$.
• Then $2^{k+1}=2\cdot2^k$ hence $2^{k+1}\geqslant2\cdot(3k^2+5)$.
• Furthermore, $2\cdot(3k^2+5)\geqslant3(k+1)^2+5$ (the so-called missing step).
• Hence $2^{k+1}\geqslant3(k+1)^2+5$, which is $S(k+1)$.
-
sorry if this annoying, but why suddenly we know 2⋅(3k^2+5) >= 3(k+1)^2+5, is it just take from the statement earlier of S(k+1) : 2^k+1 >= 3(k+1)^2+5 . –  Kai Nov 15 '12 at 15:18
Suddenly is odd, since the second sentence of the post proves this. Did you check that $2(3k^2+5\geqslant3(k+1)^2+5$ if and only if $3k^2-6k+2\geqslant0$? –  Did Nov 15 '12 at 15:20
if you mean substitute k = 8 into the inequality is checking then yes, but what i dont understand is the connection between 3(k+1)^2+5 and 2⋅(3k^2+5), 2⋅(3k^2+5) >= 3(k+1)^2+5 is true, just how it jump to there, deeply sorry if this is disturbing –  Kai Nov 15 '12 at 15:42
I certainly never said THAT. Once again, you consider an inequality I(k): (2(3k^2+5)⩾3(k+1)^2+5) and another inequality J(k): (3k^2−6k+2⩾0). These can be true, or not, and as a matter of fact, for some k, I(k) is true and for others I(k) is false, likewise for J(k). But the thing is that, IF J(k) holds for some k THEN I(k) holds for the same k. Once you noted that, you pick some k⩾8. Obviously J(k) holds for this k. Hence I(k) holds for this same k. And this shows that, IF S(k) holds for some k⩾8, then S(k+1) holds as well. –  Did Nov 15 '12 at 16:33
ok, guess i have to do more to fully master this, thank you, your explanation is helpful –  Kai Nov 15 '12 at 16:38

Observe that since $k\ge8>6$, then $$3(k+1)^2+5=3k^2+6k+8<3k^2+k^2+8=4k^2+8<6k^2+8<6k^2+10.$$

Rewriting the far right expression as $2(3k^2+5)$, we use the fact that $S(k)$ holds (and the fact that multiplication by $2$ preserves order) to conclude that $$3(k+1)^2+5<2(3k^2+5)\leq 2(2^k)=2^{k+1},$$ so $S(k+1)$ holds.

-
Thanks for your pointer - I can't believe I wrote what I wrote! I hate to do anything to further confuse an OP! (answer deleted!). –  amWhy Nov 15 '12 at 15:14
Been there! (Recently....) –  Cameron Buie Nov 15 '12 at 15:16
thank you, only the part 2⋅(3k^2+5) >= 3(k+1)^2+5 im still cannot get it,why we can assume 2⋅(3k^2+5) >= 3(k+1)^2+5, i substitute k=8 and it is correct, but what is connection between 3(k+1)^2+5 and 2⋅(3k^2+5). deeply sorry if this is disturbing –  Kai Nov 15 '12 at 15:37
@Kai: Since $$3(k+1)^2+5<6k^2+10=2(3k^2+5),$$ as shown above. Note that we're not assuming this. We're justifying it. Is there a step in the chain that you don't understand? –  Cameron Buie Nov 15 '12 at 15:45
i understand this, just the 3(k+1)^2+5 < 6k^2 +10 is confusing for me because why the part 6k^2 +10 can link to 3(k+1)^2+5 –  Kai Nov 15 '12 at 15:52