1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inductive proof 4^n >/ n^4

  1. Nov 5, 2011 #1
    1. The problem statement, all variables and given/known data
    n is an element of the Natural numbers, and n [itex]\geq5[/itex], then 4^n [itex]\geq(n^4)[/itex]


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


    3. 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?
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Nov 5, 2011 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    What have you tried?
     
  4. Nov 5, 2011 #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?
     
  5. Nov 5, 2011 #4
    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: Nov 5, 2011
  6. Nov 5, 2011 #5

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    shaon0,

    Do you realize that you are not supposed to give complete solutions?
     
  7. Nov 5, 2011 #6
    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.
     
  8. Nov 5, 2011 #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.
     
  9. Nov 5, 2011 #8
    Yes, that's true but how would you have proven 2^n>n^2? As an extension; k^n>n^k for n,kEZ+
     
  10. Nov 7, 2011 #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?
     
  11. Nov 7, 2011 #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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Inductive proof 4^n >/ n^4
Loading...