Proof method and for $5^n > n+4^n$, for $n\ge2$

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?

-
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
One way: $5=4+1$. Now use the Binomial Theorem and estimate. –  David Mitra Mar 20 '12 at 15:15
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

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

-
Thank you, @pedja. I can see the approach you took to reach the conclusion I needed. –  user27271 Mar 20 '12 at 15:57

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.

-
As a physicist this is how I would have approached the question. –  Pureferret Mar 20 '12 at 16:48

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,

-
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

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.

-
Got to run to my next class. –  Siddhi V Iyer Mar 20 '12 at 15:22

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

-

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.

-

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

-