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

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

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

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

${\displaystyle {}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

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

We have to show

${\displaystyle {}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 ${\displaystyle {}{\frac {1}{2}}n^{4}}$, is at least as large as the term on the right hand side. But this follows directly from ${\displaystyle {}n^{4}\geq 8n^{3}}$ (since ${\displaystyle {}n\geq 10}$), from ${\displaystyle {}n^{4}\geq 12n^{2}}$, since ${\displaystyle {}n^{2}\geq 12}$, from ${\displaystyle {}n^{4}\geq 8n}$ and from ${\displaystyle {}n^{4}\geq 2}$.