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
    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
    @Kai: Click the link in the comment above for further explanation/discussion.2012-11-15