Results 1 to 7 of 7

Thread: 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 $\displaystyle n \geq 4$, $\displaystyle 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 $\displaystyle n \in N$ and let P(n) be the statement:

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

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

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

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

    Now we consider P(k+1)

    $\displaystyle 3^{k+1} > (k+1)^3$

    $\displaystyle 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 $\displaystyle 3^k > k^3$. You also know that $\displaystyle k \geq 4$ so that gives you $\displaystyle 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 $\displaystyle 3^k > k^3$. You also know that $\displaystyle k \geq 4$ so that gives you $\displaystyle 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 ... $\displaystyle (k+1)^3 = k^3 + 1 + 3k^2 + 3k < 3^k + 1 + 3k^2 + 3k$
    you need to prove that $\displaystyle (k+1)^3 < 3^{k+1} $
    take the difference of the two inequalities. it follows that you must prove $\displaystyle 1 + 3k^2 + 3k < 2.3^k $.

    now start afresh with this inequality using the same trick. this time you will get something like $\displaystyle 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 $\displaystyle 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 $\displaystyle 2.3^k$ term from!
    So, we know $\displaystyle 3^k > k^3$ and $\displaystyle k \geq 4$, now we want to prove:

    $\displaystyle 3^{k+1} > (k+1)^3$

    $\displaystyle
    3.3^k > k^3+3k^2+3k+1
    $

    This is where I am so far. Any more explanation is appreciated.
    Last edited by Roam; Aug 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 .. $\displaystyle (k+1)^3 = k^3 + 1 + 3k^2 + 3k < 3^k + 1 + 3k^2 + 3k$

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

    the difference [(2) - (1)] of the two inequalities is $\displaystyle
    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 $\displaystyle 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; Aug 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: Jun 10th 2011, 01:13 PM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. Complete Induction proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 22nd 2009, 06:41 AM
  4. complete induction problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Oct 20th 2008, 11:48 AM
  5. proof by complete induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Sep 25th 2007, 01:09 PM

Search Tags


/mathhelpforum @mathhelpforum