# $5^n > n+4^n$ for all $n\ge2$

I need to know the effective methods for proving the following:

$5^n > n+4^n$ for all $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.

-
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

$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. – jneander Mar 20 '12 at 15:57

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

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

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

-

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.

-