Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove n^3 <= 2^n

  1. May 3, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove: n3 <= nn, n >= 10

    2. Relevant equations

    3. The attempt at a solution
    Prove by induction on n.

    i) 1 = 1

    1 < 2

    ii) n +1
    claim (n+1)3 <= 2n+1 , n >=10

    I don't know how to induct with n+1, when n >=10
  2. jcsd
  3. May 3, 2010 #2
    You shouldn't start with n = 1; your statement isn't even true for some n < 10. The problem tells you to prove it for n >= 10. So start with 10 as your base case.

    Prove that [itex] 10^3 \leq 10^{10} [/itex].

    Then prove that if [itex] n^3 \leq n^n [/itex], this means that [itex] (n+1)^3 \leq (n+1)^{n+1} [/itex].
  4. May 3, 2010 #3
    how can i connect (n+1) n+1 to 2 n+1. Can you show me how
    Last edited: May 3, 2010
  5. May 3, 2010 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    The title of the thread is to prove [itex]n^3 < 2^n[/itex] while the OP indicates that the problem is [itex]n^3 < n^n[/itex]. So which is it?
  6. May 3, 2010 #5
    Since n>=10, then P(1),P(2),P(3),P(4),P(5),P(6),P(7),P(8),P(9) are true automatically(where P is the statement). You just have to prove that P(n) would imply P(n+1). Obviously we have just done that for n=1,...,8 for n=9, we just have to prove that P(10) is true which could be done using substitution. Then, for n>=10, you just need to prove it algebraically.

    You must show that P(n) would imply P(n+1) for n>=10.

    How would you start with the statement, (n^3)<= 2^n (n=10,...) and arrive at (n+1)^3<=(2^(n+1)) ?

    (NOTE: For these types of induction questions, you have to work backwards.)
  7. May 3, 2010 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Not at all!

    Proving [itex]n^3 \le n^n[/itex] for n>10 is trivial, So let's assume the problem is to prove [itex]n^3 \le 2^n[/itex] per the title of the thread.

    n & n^3 & 2^n & P(n) \\
    0 & 0 & 1 & T \\
    1 & 1 & 2 & T \\
    2 & 8 & 4 & F \\
    3 & 27 & 8 & F \\
    4 & 64 & 16 & F \\
    5 & 125 & 32 & F \\
    6 & 216 & 64 & F \\
    7 & 343 & 128 & F \\
    8 & 512 & 256 & F \\
    9 & 729 & 512 & F

    So except for n=0 and n=1, the proposition is false for n=0..9. The proposition is nonetheless true for all n≥10.
  8. May 4, 2010 #7
    No, the statement is true for n<10. This is because the statement, P(n) states that
    "(n^3)=< 2^n OR n<=9"

    So that the statement is (obviously) true for n<10 because of the connective "OR".

    Induction must apply to every natural number, because natural are DEFINED axiomatically using induction.

    P(10) must then be verified by the condition that P(9) would imply P(10) (which happens when they both have a truth value). For n>=10, the formula must be used to verify that P(n) would indeed imply P(n+1).

    If P(1),...,P(10) were not verified to be true(by the statement, P(1) to P(9) are automatically true without any arithmetic verification), then both the conditions for induction are not met and the proof would be wrong.

    The subtleties of a proof is incredibly important in mathematics.
  9. May 4, 2010 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    You didn't say that the first time, Pinu7, and the original poster most certainly did not specify the problem this way.

    Doing this is being overly pedantic. There's nothing wrong with starting induction with a base case n that is not one and there is no reason to invent such a connective predicate in such cases.

    In any case, we aren't helping the original poster one iota with this quibbling.

    You don't. Post #2 by hgfalling was mislead by your problem statement where you said
    Given the title of the thread and later statements in the original post, it is fairly obvious that you made a typo in that problem statement. The problem is to prove that [itex]n^3 \le 2^n \,\forall n \ge 10[/itex].

    So, how to proceed?
    First, establish that the proposition is true for some base case n0. Here the base case is n0=10; you need to show that [itex]10^3 \le 2^{10}[/itex]. Is this true?

    Next you assume the proposition is true for some nn0 (the induction hypothesis) and show that given this assumption that the proposition also holds for n+1. In this case, you need to show that if [itex]n^3 \le 2^n[/itex] for some [itex]n\ge 10[/itex] then [itex](n+1)^3 \le 2^{n+1}[/itex].

    • Use the fact that if a≤b and b≤c then a≤c because '≤' is transitive.
      If you can find some intermediate expression bn such that (n+1)3bn and bn≤2n+1 then (n+1)3≤2n+1.
    • Use the fact that multiplying both sides of an inequality by a positive number does not change the inequality.
      Try multiplying both sides of n3≤2n by 2. This should suggests an intermediate value to use in the proof.
  10. May 4, 2010 #9
    "You are in la-la-land OR today is Tuesday." QED.

    But seriously. Nobody here apparently cares about the sufficiency of "OR" in place of conditional statements (i.e P => Q <==> -P V Q)... and I DON'T BLAME THEM!
    This is the most obscure approach to induction imaginable.
    YES, we assume the antecedent to be true, but your suggestions are confusing (others) at best.
  11. May 6, 2010 #10
    since latex on this website was being gay on me i had to use pdflatex. :smile:

    Attached Files:

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook