Prove n^3 <= 2^n: Homework via Induction

[invisible_man]

Homework Statement

Prove: n³ <= nⁿ, n >= 10

Homework Equations

The Attempt at a Solution

Prove by induction on n.

i) 1 = 1

1 < 2

ii) n +1
claim (n+1)³ <= 2ⁿ⁺¹ , n >=10

I don't know how to induct with n+1, when n >=10

 

[hgfalling]

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 10^3 \leq 10^{10}.

Then prove that if n^3 \leq n^n, this means that (n+1)^3 \leq (n+1)^{n+1}.

 

[invisible_man]

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 10^3 \leq 10^{10}.

Then prove that if n^3 \leq n^n, this means that (n+1)^3 \leq (n+1)^{n+1}.

how can i connect (n+1) ⁿ⁺¹ to 2 ⁿ⁺¹. Can you show me how

 

[D H]

The title of the thread is to prove n^3 &lt; 2^n while the OP indicates that the problem is n^3 &lt; n^n. So which is it?

 

[Pinu7]

Prove by induction on n.

i) 1 = 1

1 < 2

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.

ii) n +1
claim (n+1)³ <= 2ⁿ⁺¹ , n >=10

I don't know how to induct with n+1, when n >=10

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.)

 

[D H]

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).

Not at all!

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

<br /> \begin{array}{rrrl}<br /> n &amp; n^3 &amp; 2^n &amp; P(n) \\<br /> 0 &amp; 0 &amp; 1 &amp; T \\<br /> 1 &amp; 1 &amp; 2 &amp; T \\<br /> 2 &amp; 8 &amp; 4 &amp; F \\<br /> 3 &amp; 27 &amp; 8 &amp; F \\<br /> 4 &amp; 64 &amp; 16 &amp; F \\<br /> 5 &amp; 125 &amp; 32 &amp; F \\<br /> 6 &amp; 216 &amp; 64 &amp; F \\<br /> 7 &amp; 343 &amp; 128 &amp; F \\<br /> 8 &amp; 512 &amp; 256 &amp; F \\<br /> 9 &amp; 729 &amp; 512 &amp; F<br /> \end{array}<br />

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.

 

[Pinu7]

Not at all!

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.

 

[D H]

No, the statement is true for n<10. This is because the statement, P(n) states that
"(n^3)=< 2^n OR n<=9"

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.

how can i connect (n+1) ⁿ⁺¹ to 2 ⁿ⁺¹.

You don't. Post #2 by hgfalling was mislead by your problem statement where you said

Prove: n³ <= nⁿ, n >= 10

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 n^3 \le 2^n \,\forall n \ge 10.

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

Next you assume the proposition is true for some n≥n₀ (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 n^3 \le 2^n for some n\ge 10 then (n+1)^3 \le 2^{n+1}.


Hints:

• Use the fact that if a≤b and b≤c then a≤c because '≤' is transitive.
  If you can find some intermediate expression b_n such that (n+1)³≤b_n and b_n≤2ⁿ⁺¹ then (n+1)³≤2ⁿ⁺¹.
• Use the fact that multiplying both sides of an inequality by a positive number does not change the inequality.
  Try multiplying both sides of n³≤2ⁿ by 2. This should suggests an intermediate value to use in the proof.

 

[The Chaz]

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.

"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.

 

[showzeb110]

since latex on this website was being gay on me i had to use pdflatex.