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!

Proof by induction

  1. May 3, 2016 #1
    1. The problem statement, all variables and given/known data
    Prove that 3^n>n^4 for all n in N , n>=8

    2. Relevant equations



    3. The attempt at a solution
    Base case: 3^8>8^4

    Inductive step
    Assume 3^n>n^4. Show 3^n+1>(n+1)^4
    I tried a lot of approaches to get from the inductive hypothesis to what I want to show

    Ex:
    3^n>n^4
    3^n+1>3n^4
    3n^4>(3n^4)-3=3(n^4-1)=3((n^2)-1)((n^2)+1)=3(n+1)(n-1)(n^2+1)>3(n+1)(n-1)(n^2-1)
    =3(n+1)(n-1)(n+1)(n-1)=3((n+1)^4-(n-1)^4)

    It looks like I went too far

    My other approach is this. It looks a little bit crazy, but I think it works

    3^n+1>n^4+2*3^n

    I will show that n^4+2*3^n grows faster than (n+1)^4 by using limits and loopitals rule.
     
    Last edited: May 3, 2016
  2. jcsd
  3. May 3, 2016 #2

    fresh_42

    Staff: Mentor

    Have you tried to expand ##(n+1)^4## with the binomial formula and then substitute the powers of ##n## by your inductive hypothesis? And remember that ##n ≥ 8##.
     
  4. May 3, 2016 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    From ##3^n > n^4## it does not follow that ##3^n+1 > (n+1)^4##, which is what you wrote. If you mean ##3^{n+1} > (n+1)^4##, then use parentheses, like this: 3^(n+1) > (n+1)^4.
     
  5. May 3, 2016 #4
    yes sorry, so how do I do it?
     
  6. May 3, 2016 #5

    fresh_42

    Staff: Mentor

    Read my post. You can as well find an upper bound for ##(n+1)^4## as a lower for ##3^{n+1}##.
    I think it works.
     
  7. May 3, 2016 #6
    sorry I just scroll down. Ummm so (n+1)^4=n^4+4n^3+6n^2+4n+1. Do I have to go from what I have to show to the inductive hypothesis?
     
  8. May 3, 2016 #7

    fresh_42

    Staff: Mentor

    Yes, here you can substitute the powers of ##n## with the inductive hypothesis, e.g. ##4n^3 < 4 \frac{3^n}{n}##. Plus the lower bound on ##n## gives an upper bound on ##\frac{1}{n}##.
     
  9. May 3, 2016 #8
    how does that maintain the inequality?. For example, 3^(n+1)>n^4+4n^3+6n^2+4n+1. I am just allowed to replace values smaller than n.
     
  10. May 3, 2016 #9

    fresh_42

    Staff: Mentor

    But you can as well start with ##(n+1)^4## and make it bigger as long as you stay below ##3^{n+1}##, don't you?
     
  11. May 3, 2016 #10
    4n^3<4*3^n/n
    n^4<3^n
    6n^2<6*3^n/n^2
    4n<4*3^n/n^3
    1<3^n/n^4
    and then you add them, but how do I show that 3^n+1 is greater than the resulting inequality.
     
  12. May 3, 2016 #11

    fresh_42

    Staff: Mentor

    Already said. You have an upper bound for ##\frac{1}{n}##, too. Now go ahead and really add the terms. Is there a common factor? How big are the remaining terms? (Hint: leave the 1 alone there's space enough.)
     
  13. May 4, 2016 #12

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    When you go from ##3^n## to ##3^{n+1}## you multiply by 3; when you go from ##n^4## to ##(n+1)^4## you multiply by ##(\frac{n+1}{n})^4 = ( 1 + \frac{1}{n})^4##. As long as you have ##3 \geq (1 + \frac{1}{n})^4## your induction step should be OK.
     
  14. May 4, 2016 #13

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    It looks using this should work nicely.

    ##3n^4=n^4+n^4+n^4\ ## Yes, that's pretty much trivial.

    Then to show that ##\ 3n^4 > n^4+4n^3+6n^2+4n+1 \,,\ ## compare the following:
    ##n^4\ ## and ##\ n^4\,,\ ## trivial
    ##n^4\ ## and ##\ 4n^3+4n\,,\ ## remembering n ≥ 8 .
    ##n^4\ ## and ##\ 6n^2+1\,,\ ## remembering n ≥ 8 .​
    .
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof by induction
  1. Proof By Induction (Replies: 2)

  2. Proof by induction (Replies: 1)

  3. Induction Proofs (Replies: 3)

  4. Induction Proof (Replies: 11)

  5. Induction proof (Replies: 4)

Loading...