1
$\begingroup$

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.

2 Answers 2

1

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)$.
  • 0
    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 .2012-11-15
  • 0
    *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$?2012-11-15
  • 0
    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 disturbing2012-11-15
  • 0
    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.2012-11-15
  • 0
    ok, guess i have to do more to fully master this, thank you, your explanation is helpful2012-11-15
1

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.

  • 0
    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!).2012-11-15
  • 0
    Been there! (Recently....)2012-11-15
  • 0
    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 disturbing2012-11-15
  • 0
    @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?2012-11-15
  • 0
    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+52012-11-15
  • 0
    @Kai: We showed this in the following steps: $$3(k+1)^2+5=3k^2+2k+8\tag{1}$$ $$3k^2+2k+8<3k^2+2k+10\tag{2}$$ $$3k^2+2k+10<3k^2+k^2+10\tag{3}$$ $$3k^2+k^2+10=4k^2+10\tag{4}$$ $$4k^2+10<6k^2+10\tag{5}$$ Are there any steps you don't understand?2012-11-15
  • 0
    i understand this, is the way it change i dont understand, for example 6K^2 +10 < 4k^2 +10, how we know 6K^2 become 4k^22012-11-15
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6435/discussion-between-cameron-buie-and-kai)2012-11-15
  • 0
    @Kai: Click the link in the comment above for further explanation/discussion.2012-11-15