Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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)$.
share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.