0
$\begingroup$

If $ n $ is a natural number and $n \geq 4$ then $3^n > 2n^2 +3n$. Note* The inequality is false when $ n=1,2, $ and $ 3 $. I understand how to prove the base case. I'm having trouble proving the induction step for $ P(k+1) $ . I'm not sure how to get $ (k+1) $ on both sides to prove the inequality is true. Any ideas on how to get started? Thanks.

$\endgroup$
0
$\begingroup$

Suppose that $3^n > 2n^2 + 3n$ for some natural $n \ge 4$. Then you want to prove that $3^{n+1} > 2(n+1)^2 + 3(n+1)=2n^2+4n+2+3n+3=2n^2+3n+4n+5$.

Hence, you just need to prove that $2(3)^n>4n+5 $ for all $n \ge 4$, after you have completed your base case.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

$3^k > 2k^2 + 3k$ given. We want that $3^{k+1} > 2k^2 + 4k+2+3k+3 = 2k^2+7k+5$ .Now, multiply both sides by $3$: We get $3^{k+1} > 6k^2 + 9k$.

Now, note that $6k^2 + 9k - 2k^2-7k-5 = 4k^2 + 2k - 5 = \frac{(4k+1)^2-21}{4}$.

Hence, whenever $(4k+1)^2 > 21$, it follows that $3^{k+1} > 6k^2 + 9k > 2k^2+7k+5$. but $(4k+1)^2 > 21 \iff k > \frac{\sqrt{21} - 1}{4} \approx 0.89$. Hence, this applies for all positive integral $k$, and therefore for all $k \geq 4$.

The base case is just $$ 3^4 = 81 > 44 = 32 + 12 = 2 \times 4^2 + 3 \times 4 $$

Thus, we are done with the inductive step.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ why did you subtract what we got from what we want?? $\endgroup$ – ash Oct 26 '16 at 1:23
  • $\begingroup$ See, if $B - C > 0$ then $B > C$ and vice versa. We want to show that $3^{k+1} > 2(k+1)^2 + 3(k+1)$. I do this by trying to find a quantity in the middle of these two, which is $6k^2+9k$. I show that $3^{k+1} > 6k^2+9k$, but then I also show that $6k^2 + 9k > 2k^2+7k+5$ by showing that the difference is greater than zero. Then, we get that this $6k^2+9k$ is in the middle of the two quantities we want to compare. $\endgroup$ – астон вілла олоф мэллбэрг Oct 26 '16 at 1:26
0
$\begingroup$

Let $S(n)$ be the statement $(n\in \Bbb N \land 3^n>2n^2+3n).$ We have $$S(n)\implies 3^n\geq 2n^2+3n+1\implies$$ $$\implies 3^{n+1}=3\cdot 3^n\geq 3(2n^2+3n+1).$$ Now we also have $$3(2n^2+3n+1)>2(n+1)^2+3(n+1)\iff $$ $$\iff 6n^2+9n+3>2n^2+7n+5\iff$$ $$\iff 4n^2+2n>2,$$ and this last inequality holds for all $n\in \Bbb N.$ So for all $n\in \Bbb N$ we have $S(n) \implies 3^{n+1}\geq 3(2n^2+3n+1)>$ $>2(n+1)^2+3(n+1).$

That is, $S(n)\implies S(n+1).$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ We do not really need to strengthen $3^n>2n^2+3n$ to $3^n\geq 2n^2+3n+1$ because $3(2n^2+3n)>2(n_1)^2+3(n+1)\iff 4n^2+2n>5 ,$ and this last inequality hold for all $n\in \Bbb N.$ But it is a useful tool in other Q's. $\endgroup$ – DanielWainfleet Sep 28 '18 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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