Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
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

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
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
ohh. It makes sense now. Thanks! –  E.O. Nov 5 '11 at 1:54
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

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.

share|improve this answer
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
Well, that's a typical me!Thanks for pointing that out.I never understand how I manage to make things so complex. –  Eisen Nov 4 '11 at 17:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.