- #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
how can i connect (n+1) n+1 to 2 n+1. Can you show me howhgfalling 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].
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.invisible_man said:Prove by induction on n.
i) 1 = 1
1 < 2
You must show that P(n) would imply P(n+1) for n>=10.ii) n +1
claim (n+1)3 <= 2n+1 , n >=10
I don't know how to induct with n+1, when n >=10
Not at all!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).
D H said:Not at all!
You didn't say that the first time, Pinu7, and the original poster most certainly did not specify the problem this way.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 don't. Post #2 by hgfalling was mislead by your problem statement where you saidinvisible_man said:how can i connect (n+1) n+1 to 2 n+1.
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].invisible_man said:Prove: n3 <= nn, n >= 10
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.
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.
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.
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.
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.
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.