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 need to know the effective proof methods for proving the following:

$$5^n > n+4^n, ~~\mbox{for}~~~ n\ge2$$

A solution would be helpful. Even more helpful would be a breakdown of the thinking that leads to the solution. I'd like to be able to figure these out on my own.

I've been struggling with mathematical proofs and haven't been able to figure out some of the problems I've been assigned. Also, is there a general label or name for this type of statement?

share|improve this question
    
Use mathematical Induction. –  user9413 Mar 20 '12 at 15:06
    
Show at least a little bit of your work. What did you try? –  Kirthi Raman Mar 20 '12 at 15:12
1  
One way: $5=4+1$. Now use the Binomial Theorem and estimate. –  David Mitra Mar 20 '12 at 15:15
1  
I think the general label for this type of statement would be "a problem". It's not an hard enough kind of problem to classify it in some category. A statement that you want to prove for positive integers is not a very precise class of problems. –  Patrick Da Silva Mar 20 '12 at 15:19
add comment

7 Answers 7

up vote 3 down vote accepted

$1)~n=2 ;~25>18$

$2)~\text{suppose} : 5^n > n+4^n$

$3)~\text{we have to prove :} 5^{n+1} >n+1+4^{n+1}$

Since:

$5^n > n+4^n \Rightarrow 5^{n+1} > 5n+5\cdot 4^n>n+1+4^{n+1} \Rightarrow$

$\Rightarrow 5^{n+1} >n+1+4^{n+1}$

share|improve this answer
    
Thank you, @pedja. I can see the approach you took to reach the conclusion I needed. –  user27271 Mar 20 '12 at 15:57
add comment

You can solve this problem using simple techniques from calculus. We want to show that

$$5^{n} > n + 4^{n} ~~~\mbox{ for }~~~ n \geq 2$$

First, I will write $n$ as $x$ to indicate that we are working with real numbers, not just natural ones.

$$5^{x} > x + 4^{x} ~~~\mbox{ for }~~~ x \geq 2$$

Next, we evaluate this inequality at $x=2$. This becomes

$$ 25 = 5^{2} > 2 + 4^{2} = 18$$

Which is certainly true. Now, we need only to show that the left-hand side grows more quickly than the right hand side, so that the this strict inequality is maintained as $x$ increases. This is equivalent to showing that the derivative of the left-hand side is larger than the derivative of the right-hand side for $x \geq 2$. Taking derivatives, we get

$$5^{x}\log(5) > 1 + 4^{x}\log(4) ~~~\mbox{ for }~~~ x \geq 2$$

Again, at $x=2$, this just becomes

$$5^{2}\log(5) > 1 + 4^{2}\log(4) $$

which is easy to verify. We could go through the work of showing that the left-hand derivative is larger than the right-hand one, but the $1$ on the right-hand side makes this a little tricky. So, we repeat our technique above. The left-hand derivative is larger than the right-hand derivative at $x=2$. If it grows faster than the right-hand derivative for $x \geq 2$, we will be done. Thus, we take derivatives again, to obtain

$$5^{x}\log(5)\log(5) > 4^{x}\log(4)\log(4) ~~~\mbox{ for }~~~ x \geq 2$$

Which is trivially true, because every factor on the left-hand side is larger than the corresponding factor on the right-hand side. Thus, the left-hand derivative grows faster than the right hand-derivative, and thus is greater than it for $x \geq 2$, which means that the left-hand side of our original equality, $5^{x}$, is greater than the right hand side, $x + 4^{x}$, for $x \geq 2$.

Noting that the natural numbers are contained in the real ones, we are done. QED


In general, the above technique is probably not what the question wants from you. For that, you should read the other answers. This just highlights a generally useful `brute-force' way of showing such inequalities.

share|improve this answer
    
As a physicist this is how I would have approached the question. –  Pureferret Mar 20 '12 at 16:48
add comment

How about this? $$ (1+x)^n - x^n = (1+x - x)\left( \sum_{k=0}^{n-1} x^k \right) = 1 + x + \dots + x^{n-1} > 1 + 1 + \dots + 1 = n. $$

Hope that helps,

share|improve this answer
    
Perhaps the work you could try to do is understand why the first equality of my argument is true. I leave it up to you. –  Patrick Da Silva Mar 20 '12 at 15:19
add comment

For $n=2$, $5^2-4^2 > 2$ so the result is true for $n=2$

Assume the result $5^m-4^m > m$ is true

$$ \begin{align*} 5^{m} > 4^{m}+m \Rightarrow 5^{m+1}-4^{m+1} &> 5(4^{m}+m)-4.4^{m}\\ &>( 4^{m}+5m )> (m+1) \\ \end{align*} $$

Q.E.D.

share|improve this answer
    
Got to run to my next class. –  Siddhi V Iyer Mar 20 '12 at 15:22
add comment

Hint: $\ $ Put $\rm\:x,y = 5,4\:$ in $\rm\ x^n-y^n = \:(x-y)\:\sum x^k y^{n-1-k}\: >\: n(x-y)\:$ if $\rm\ y\ge1,\ x,n>1$ since this implies that the sum $\rm > n,\:$ having $\rm\:n\:$ terms $\ge 1,\:$ with one strict: $\rm\:x^{n-1} \ge x > 1$.

share|improve this answer
add comment

Divide both sides by $4^n$. We must show that $(\frac{5}{4})^n > \frac{n}{4^n} + 1$ for all $n \geq 2$.

This is clearly true for $n=2$. Now, the left-hand side is obviously increasing with $n$, while the right-hand side is decreasing (since $\frac{n+1}{4^{n+1}} = \frac{(n+1)/4}{4^n} < \frac{n}{4^n}$ for $n \geq 1$). QED.

share|improve this answer
add comment

$$5^n= 5*5^{n-1} > 5*4^{n-1}=(1+4)*4^{n-1}=4^{n-1}+4^n$$

Now observe that for $n \geq 2$ we have

$$\frac{4^{n-1}+n-2}{n-1}=\frac{4^{n-1}+1+..+1}{n-1} \geq \sqrt[n-1]{4^{n-1}}=4$$

Thus

$$4^{n-1} \geq 4n-4-n+2=3n-2\geq n$$

Combining these two we get

$$5^n > 4^n+4^{n-1} \geq 4^n+n$$

share|improve this answer
add comment

Your Answer

 
discard

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.