Showing $4^m>2m^2 + 5m$ for $m\geq 3$ by induction

Question

Show that $4^m>2m^2 + 5m$. I want to practice proving by induction. I know that this is not true for small values of $m$. So, the base case can be $m=3$. Then we have $$4^3 > 2(3)^2+5(3)$$ = $$64>32$$ Next, we say if $$4^m>2m^2 + 5m$$ then $$4^{m+1}>2(m+1)^2 + 5(m+1)$$

= $$4^m(4) >(m+1)(2(m+1)+1)$$

I am not quite certain what to do with this from here.

Answer 1

You have already established the base case. Now, let $S(m)$ denote the following proposition for all $m\geq 3$: $$ S(m) : 4^m>2m^2+5m. $$ Fix some $k\geq 3$ and assume that $$ S(k) : 4^k>2k^2+5k $$ holds. To be shown is that $S(k+1)$ follows: $$ S(k+1) : 4^{k+1} > 2(k+1)^2+5(k+1). $$ Starting with the left-hand side of $S(k+1)$, \begin{align} 4^{k+1} &= 4\cdot 4^k\tag{by definition}\\[0.5em] &> 4\cdot(2k^2+5k)\tag{by $S(k)$}\\[0.5em] &= 8k^2+20k\tag{expand}\\[0.5em] &> 2k^2+9k+7\tag{"strategic observation"}\\[0.5em] &= 2(k^2+2k+1)+5k+5\tag{strategically rearrange}\\[0.5em] &= 2(k+1)^2+5(k+1), \end{align} we see that the right-hand side of $S(k+1)$ follows.

Thus, by mathematical induction, $S(m)$ holds for all $m\geq 3$. $\blacksquare$

---

I should probably note how I came to my "strategic observation." Essentially, I myself got to the "expand" step and wondered what I might need next. Knowing that I ultimately needed to end up at $2(k+1)^2+5(k+1)$, I expanded everything for this sum and essentially worked backwards, showing what I needed and where. Does it make sense now?

Answer 2

Here is how you can reach case $m+1$ by assuming case $m$:

$$4^m>2m^2 + 5m\\ \Rightarrow4(4^m)>4(2m^2 + 5m)\\ \begin{align}\Rightarrow4^{m+1}&>8m^2+20m\\ &=2m^2+9m+6m^2+11m\\ &>2m^2+9m+7\\ &=2m^2+4m+2+5m+5\\ &=2(m^2+2m+1)+5m+5\\ &=2(m+1)^2+5(m+1) \end{align}$$