Results 1 to 7 of 7

Math Help - Complete/Simple Induction

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    191

    Complete/Simple Induction

    Here's the question:

    Use induction to prove that for every integer n \geq 4, 3^n > n^3.


    Firstly, I'm confused whether to use the simple induction or the complete induction for this problem. I will try the simple one:

    Base case: let n \in N and let P(n) be the statement:

    " n \geq 4, 3^n > n^3"

    Since n \geq 4 I can't use P(1) as the base case so I'll do P(4) in its stead:

    3^4 > 4^3 \Rightarrow 81>64

    Inductive step:
    Suppose k \geq 4 and P(k) is true. So 3^k > k^3

    Now we consider P(k+1)

    3^{k+1} > (k+1)^3

    LHS = 3^k .3 > k^3 +1 = RHS

    What else can be done here to prove the inequality?

    any help is appreciated
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    You know from the base case that 3^k > k^3. You also know that k \geq 4 so that gives you 3^{k+1} = 3 \cdot 3^k > 3k^3 > 2k^3 + 1 > k^3 + 1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2009
    Posts
    67
    Quote Originally Posted by Defunkt View Post
    You know from the base case that 3^k > k^3. You also know that k \geq 4 so that gives you 3^{k+1} = 3 \cdot 3^k > 3k^3 > 2k^3 + 1 > k^3 + 1

    errr ... the 1 must be inside the ()^3 .. i will write more in a new reply
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Aug 2009
    Posts
    67
    OK .. i am using plain english as i have not yet figured out how to put the mathematical letters.

    so write (k+1)^3 = k^3+1+3k^2+3k > 3^k +3k^2+3k

    so if you prove that 3^(k+1)-3^k = 2.3^k > 3k^2 + 3k then you are through.

    apply the same trick of starting with the polynomial. this time again you have to compare a polynimal of lesser degree with a exponential. go on till what remains is obvious. i hope i have made it clear. just write whatever i have told you on a piece of paper .. you will get it.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2009
    Posts
    67
    ok see this ...  (k+1)^3 = k^3 + 1 + 3k^2 + 3k < 3^k + 1 + 3k^2 + 3k
    you need to prove that  (k+1)^3  < 3^{k+1}
    take the difference of the two inequalities. it follows that you must prove   1 + 3k^2 + 3k < 2.3^k .

    now start afresh with this inequality using the same trick. this time you will get something like  6k+8 < 4.3^k . again do the same step. ignore any mistakes that i may have done ... the essential point is that degree of the polynomial keeps reducing whereas the exponential stays same.

    remember that each time your applicable  k has a different domain. so just keep track of it.

    perhaps you may have recognized what i am essentially doing. i am replicating the way of taking derivatives in a continuous setup to the discrete setup that you need.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2008
    Posts
    191
    Frankly, that doesn't make a whole lot of sense to me, I'm so confused and I can't follow where you got the 2.3^k term from!
    So, we know 3^k > k^3 and k \geq 4, now we want to prove:

    3^{k+1} > (k+1)^3

     <br />
3.3^k > k^3+3k^2+3k+1<br />

    This is where I am so far. Any more explanation is appreciated.
    Last edited by Roam; August 25th 2009 at 09:42 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Aug 2009
    Posts
    67
    maybe i will have to write in detail

    i hope you have got his far ..  (k+1)^3 = k^3 + 1 + 3k^2 + 3k < 3^k + 1 + 3k^2 + 3k

    frm this u get  (k+1)^3 - 1 - 3k^2 - 3k < 3^k -- (1)
    u need to prove  (k+1)^3  < 3^{k+1} = 3.3^k --- (2)

    the difference [(2) - (1)] of the two inequalities is   <br />
1 + 3k^2 + 3k  < 3.3^k - 3^k = 2.3^k --- (3)

    now observe that if (1) and (3) is true then (2) must be true.

    so the thing to prove now is   1 + 3k^2 + 3k  < 2.3^k . forget about the earlier inequality and instead treat this as your problem. in mathamatical language we say the the problem has been reduced to a new problem

    to prove this again form 3 inequalities like above .. you will get a new inequality which is even simpler. finally you will get something which is just obvious. just try it with a pen and paper.

    edit :: when i say the inequality is simpler i mean the degree of the polynomial part is smaller, even if the expression is a bigger one the polynomial itself is simpler to analyze.
    Last edited by nirax; August 26th 2009 at 12:49 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Complete Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 10th 2011, 01:13 PM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Complete Induction proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 22nd 2009, 06:41 AM
  4. complete induction problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 20th 2008, 11:48 AM
  5. proof by complete induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 25th 2007, 01:09 PM

Search Tags


/mathhelpforum @mathhelpforum