Induction/3^n \geq n^4/Exercise/Solution

Initial step for ${}n=10$. We have

${}3^{10}=9^{5}=81\cdot 81\cdot 9\geq 6000\cdot 9\geq 10000=n^{4}\,.$

For the induction step let ${}n\geq 10$. Then

${}3^{n+1}=3\cdot 3^{n}\geq 3\cdot n^{4}=n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}\,.$

On the other hand the general binomial formula yields

${}(n+1)^{4}=n^{4}+4n^{3}+6n^{2}+4n+1\,.$

We have to show

${}n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}\geq n^{4}+4n^{3}+6n^{2}+4n+1\,.$

The first summands coincide on the left and on the right. For the other summands we show that the term on the left hand side, namely ${}{\frac {1}{2}}n^{4}$, is at least as large as the term on the right hand side. But this follows directly from ${}n^{4}\geq 8n^{3}$ (since ${}n\geq 10$), from ${}n^{4}\geq 12n^{2}$, since ${}n^{2}\geq 12$, from ${}n^{4}\geq 8n$ and from ${}n^{4}\geq 2$.

To the exercise