# Using induction to prove propositions involving exponents of x

I am working on a chapter on mathematical induction. I came across a problem which seemed relatively simple, but I was unable to prove. My understanding of inductions is that if you have the equation $U_n$ and you can prove that $U_1$ is true and $U_{n+1}$ is true, you have proved the statement. My question is how to prove that $5^n\ge1+4n$. How would I approach it? Do I simply show that $(5*5^n \ge 1+4n+4)=(5^{n+1} \ge 1+4(n+1))$ which does not really prove anything. What process would i need to go through to prove the statement. Similarily, how would I approach $n!\ge 2^n$ for $n ∈ Z$, $n \ge 4$

-
The community here will be better able to help you if you tell where precisely you are getting stuck in this problem. –  Austin Mohr Nov 4 '11 at 12:26
@AustinMohr I'll modify the question –  E.O. Nov 4 '11 at 12:28
For the first, you can observe that $5^1 \ge 1+4\cdot 1$, so it is true for $n=1$. Then you want to prove that for any $n$, $U_n \implies U_{n+1}$. So assume you are given $5^n \ge 1+4n$ Now $5^{n+1}=5\cdot 5^n \ge 5(1+4n) = 1+4+5\cdot4n \gt 1+4+4n=1+4(n+1)$ and we have proven $U_{n+1}$
When you wrote $5*5^n \ge 5(1+4n)$, where did the 5 come from on the right hand side? –  E.O. Nov 5 '11 at 1:24
The $5$ on the right is the one without the exponent $n$ on the left. I used the induction assumption $5^n \ge 1+4n$ and substituted $1+4n$ for the $5^n$. –  Ross Millikan Nov 5 '11 at 1:50
This is a pretty general technique. Start with one side of U_{n+1}$, work it to split out the same side of$U_n$, make the replacement that$U_n$gives you, and work the remaining to get the other side of$U_{n+1}$. Those are exactly the steps I followed here. – Ross Millikan Nov 5 '11 at 15:14 add comment Using Mr Millikan's trick,you may try to prove that$(n+1)!\ge 2^{n}(n+1)\ge2^n\cdot 2\sqrt{n}\ge 2^{n+1}$by the AM-GM inequality. - You really don't need that$\sqrt(n)$there in the middle of your inequality, @Hermit. – Thomas Andrews Nov 4 '11 at 14:00 Probably yes.But it makes the inequality sharper. – Eisen Nov 4 '11 at 14:34 At the cost of adding complexity that is completely unnecessary - you're still only trying to prove$n+1\geq 2\$, and it makes the reader go "what the heck is that doing there?" –  Thomas Andrews Nov 4 '11 at 14:36