• Support PF! Buy your school textbooks, materials and every day products Here!

Inductive proof 4^n >/ n^4

  • #1

Homework Statement


n is an element of the Natural numbers, and n [itex]\geq5[/itex], then 4^n [itex]\geq(n^4)[/itex]


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?

Homework Statement





Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,253
972

Homework Statement


n is an element of the Natural numbers, and n [itex]\geq5[/itex], then 4^n [itex]\geq(n^4)[/itex]


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

Homework Equations



The Attempt at a Solution

What have you tried?
 
  • #3
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?
 
  • #4
48
0
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:
  • #5
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,253
972
shaon0,

Do you realize that you are not supposed to give complete solutions?
 
  • #6
48
0
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.
 
  • #7
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.
 
  • #8
48
0
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+
 
  • #9
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[itex]\geq5,[/itex], 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[itex]\geq5[/itex]:

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 [itex]\geq5[/itex]. 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 [itex]\geq5[/itex]. This completes the proof of the original inequality.

----------------------------------------
By the way, what does RTP stand for?
 
  • #10
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?
 

Related Threads on Inductive proof 4^n >/ n^4

  • Last Post
Replies
3
Views
3K
Replies
4
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
6
Views
734
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
8
Views
2K
Top