1
$\begingroup$

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$

  • 0
    @AustinMohr I'll modify the question2011-11-04

2 Answers 2

1

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

  • 0
    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.2015-07-09
0

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.

  • 0
    Well, that's a typical me!Thanks for pointing that out.I never understand how I manage to make things so complex.2011-11-04