# Inductive proof 4^n >/ n^4

IntroAnalysis

## Homework Statement

n is an element of the Natural numbers, and n $\geq5$, then 4^n $\geq(n^4)$

## Homework Equations

Base case: n=5, then 4^5=1024 >or= 5^4=625 as required.

## The Attempt at a Solution

Inductive step, assume k is an element of Natural numbers and 4^k > or = k^4.
Then we must show 4^(k+1) > or = (K+1)^4

What's the trick to showing this?

Staff Emeritus
Homework Helper
Gold Member

## Homework Statement

n is an element of the Natural numbers, and n $\geq5$, then 4^n $\geq(n^4)$

## Homework Equations

Base case: n=5, then 4^5=1024 ≥ 5^4=625 as required.

## The Attempt at a Solution

Inductive step, assume k is an element of Natural numbers and 4^k ≥ k^4.
Then we must show 4^(k+1) ≥ (k+1)^4

What's the trick to showing this?
1. The problem statement, all variables and given known data

## The Attempt at a Solution

What have you tried?

IntroAnalysis
I know that 4^(k + 1) =4(4^k) which helps since we know 4^k >/ k^4,

But (k + 1)^4 = k^4 + 4k^3 + 6k^2 + 2k + 1, and I don't know how to break this up

to show 4(4^k) >/ k^4 + 4k^3 + 6k^2 + 2k + 1
Any hints?

shaon0
I know that 4^(k + 1) =4(4^k) which helps since we know 4^k >/ k^4,

But (k + 1)^4 = k^4 + 4k^3 + 6k^2 + 2k + 1, and I don't know how to break this up

to show 4(4^k) >/ k^4 + 4k^3 + 6k^2 + 2k + 1
Any hints?

RTP: 4n>n4 for all n≥5.
I'll skip the trivial n=5 case.

S(k): Assume; 4k>k4 for all k≥5.

S(k+1): RTP: 4k+1>(k+1)4
LHS=4k+1=4k*4>k4*4=4k4

Now consider; y=4x^4-(x+1)^4; Differentiate this and see what you can deduce for x≥5. Remember to restrict y after this to use on the induction. In restricting, change the domain and co-domain to an integer field.

Last edited:
Staff Emeritus
Homework Helper
Gold Member
shaon0,

Do you realize that you are not supposed to give complete solutions?

shaon0
shaon0,

Do you realize that you are not supposed to give complete solutions?

Yeah, sorry. Uhm, just told by a mod. Deleting the post. Sorry. He's not online, so hopefully he hasn't seen it. I've deleted it and left a hint.

IntroAnalysis
Actually, I think I found an easier solution. Can someone comment?

We previously proved that for all n >/5, 2^n> n^2. We proved 2^(n+1) > (n+1)^2.
Now since we know that 2 > 0 and n + 1 > 0 (since n >/5), we know that we can square both sides and the inequality still holds so: (2^(n + 1))^2 = 2^(2n + 2) = 2^[2*(n+1)]
=4^(n+1) > ((n+1)^2)^2 = (n+1)^4
Hence, we have 4^(n+1) > (n+1)^4 which is what we wanted to prove.

shaon0
Actually, I think I found an easier solution. Can someone comment?

We previously proved that for all n >/5, 2^n> n^2. We proved 2^(n+1) > (n+1)^2.
Now since we know that 2 > 0 and n + 1 > 0 (since n >/5), we know that we can square both sides and the inequality still holds so: (2^(n + 1))^2 = 2^(2n + 2) = 2^[2*(n+1)]
=4^(n+1) > ((n+1)^2)^2 = (n+1)^4
Hence, we have 4^(n+1) > (n+1)^4 which is what we wanted to prove.

Yes, that's true but how would you have proven 2^n>n^2? As an extension; k^n>n^k for n,kEZ+

IntroAnalysis
Base case n = 5: 2^n (= 32) > n^2 (=25) is true as required.

Now we assume that the statement is true for some n an element of Natural numbers, n$\geq5,$, and show that it must be true for n + 1. We know n2< 2n and therefore 2n2<2n+1.
We are now going to use that 2n + 1 < n2 which is true for all
n$\geq5$:

2n + 1 < n2 implies n2+2n +1 < 2n2< 2n+1 and therefore (n + 1)2< 2n+1.

We are therefore done if we can demonstrate that 2n +1 < n2 for all n $\geq5$. This inequality is equivalent to 2 < (n - 1)2. The right side
is strictly increasing function of n for n > 1, thus (n - 1)2>(5 - 1)2= 16 > 2 for all n $\geq5$. This completes the proof of the original inequality.

----------------------------------------
By the way, what does RTP stand for?

IntroAnalysis
Now consider; y=4x^4-(x+1)^4; Differentiate this and see what you can deduce for x≥5. Remember to restrict y after this to use on the induction. In restricting, change the domain and co-domain to an integer field.

So y = 4x4 - (x+1)4 = 4x4 - (x4 + 4x3 + 6x2 + 4x +1)

Then dy/dx = 12x3 -12x2 -12x -4 = 12x(x2-x -1) - 4
For x ≥ 5, (actually for x ≥ 2), dy/dx is positive. Thus, 4(x+1)must be greater than (x + 1)4. Is that it?