# How to start the induction step for an inequality.

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.

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.

$$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.

• why did you subtract what we got from what we want?? – ash Oct 26 '16 at 1:23
• 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. – астон вілла олоф мэллбэрг Oct 26 '16 at 1:26

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).$$

• 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. – DanielWainfleet Sep 28 '18 at 6:36