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

  • Thread starter invisible_man
  • Start date
In summary, the problem is to prove that n^3 \le 2^n \,\forall n \ge 10. To do this, you must establish that the proposition is true for the base case n0=10, and then use the induction hypothesis to show that if the proposition holds for some n≥n0, then it also holds for n+1. This can be done by finding an intermediate value bn such that (n+1)3≤bn and bn≤2n+1, and using the fact that multiplying both sides of an inequality by a positive number does not change the inequality.
  • #1
invisible_man
16
0

Homework Statement



Prove: n3 <= nn, 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)3 <= 2n+1 , n >=10

I don't know how to induct with n+1, when n >=10
 
Physics news on Phys.org
  • #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].
 
  • #3
hgfalling said:
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].
how can i connect (n+1) n+1 to 2 n+1. Can you show me how
 
Last edited:
  • #4
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?
 
  • #5
invisible_man said:
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)3 <= 2n+1 , 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.)
 
  • #6
Pinu7 said:
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 [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.

[tex]
\begin{array}{rrrl}
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
\end{array}
[/tex]

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.
 
  • #7
D H said:
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.
 
  • #8
Pinu7 said:
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.


invisible_man said:
how can i connect (n+1) n+1 to 2 n+1.
You don't. Post #2 by hgfalling was mislead by your problem statement where you said
invisible_man said:
Prove: n3 <= nn, 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 [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].


Hints:
  • 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.
 
  • #9
Pinu7 said:
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.
 
  • #10
since latex on this website was being gay on me i had to use pdflatex. :smile:
 

Attachments

  • apply.pdf
    24.7 KB · Views: 399

1. What is the purpose of proving n^3 <= 2^n?

The purpose of this proof is to show that for all natural numbers n, the statement n^3 <= 2^n is true. This is important because it demonstrates a mathematical relationship between these two functions and can be used to solve various problems in fields such as computer science and engineering.

2. What is induction and why is it used in this proof?

Induction is a mathematical proof technique that is used to show that a statement is true for all natural numbers. It involves proving a base case, typically n = 0 or n = 1, and then showing that if the statement is true for some n, it is also true for n+1. Induction is used in this proof because it allows us to generalize the statement n^3 <= 2^n for all natural numbers, rather than having to prove it individually for each value of n.

3. How is the base case of this proof established?

The base case for this proof is n = 1. Substituting n = 1 into the statement n^3 <= 2^n, we get 1^3 <= 2^1, which simplifies to 1 <= 2. Since this statement is true, the base case is established.

4. What is the inductive hypothesis in this proof?

The inductive hypothesis in this proof is that for some natural number k, the statement k^3 <= 2^k is true. This is the assumption that we will use to prove that the statement is also true for k+1.

5. How is the inductive step of this proof carried out?

The inductive step involves using the inductive hypothesis to show that if the statement is true for k, it is also true for k+1. This is done by substituting k+1 into the statement n^3 <= 2^n and using algebraic manipulations to show that it is true. This completes the proof by induction, as we have shown that if the statement is true for k, it is also true for k+1, and since it is true for n = 1, it is true for all natural numbers n.

Similar threads

  • Calculus and Beyond Homework Help
Replies
17
Views
450
  • Calculus and Beyond Homework Help
Replies
6
Views
852
  • Calculus and Beyond Homework Help
Replies
7
Views
302
  • Calculus and Beyond Homework Help
Replies
1
Views
439
  • Calculus and Beyond Homework Help
Replies
15
Views
974
  • Calculus and Beyond Homework Help
Replies
1
Views
434
  • Calculus and Beyond Homework Help
Replies
1
Views
522
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
482
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
Back
Top