- #1
kathrynag
- 598
- 0
Homework Statement
need to prove by induction
[tex]2^{n-1}[/tex][tex]\leq[/tex]n!
Homework Equations
The Attempt at a Solution
I already did it for P(1) wnat to try P(k) and P(k+1)
P(K):[tex]2^{k-1}[/tex][tex]\leq[/tex]k!
(2k)!=(2k)(2k-1)(2k-2)...1mutton said:Plugging in what? What you have so far is [tex]2^k \le 2k![/tex] So is it true that [tex]2k! \le (k + 1)![/tex]? Recall the possible values of k.
kathrynag said:k! is less than (k+1)!
kathrynag said:Homework Statement
need to prove by induction
[tex]2^{n-1}[/tex][tex]\leq[/tex]n!
Homework Equations
The Attempt at a Solution
I already did it for P(1) wnat to try P(k) and P(k+1)
P(K):[tex]2^{k-1}[/tex][tex]\leq[/tex]k!
kathrynag said:1/2([tex]2^{k}[/tex])[tex]\leq[/tex]k!
mutton said:Plugging in what? What you have so far is [tex]2^k \le 2k![/tex] So is it true that [tex]2k! \le (k + 1)![/tex]? Recall the possible values of k.
kathrynag said:2k!=(2k)(2k-2)(2k-4)...2
kathrynag said:k! is less than (k+1)!
mutton said:Remember, the goal is to show that [tex]2^k \le (k + 1)![/tex]
mutton said:You just showed that (k + 1) k! = (k + 1)!, so
[tex]2^k \le 2k! ... (k + 1) k! = (k + 1)![/tex]
Fill in the blank by recalling the possible values of k.
jmarcian said:from f(k), 2k-1<k!, but let's just say that it equals that, which it does...
2k-1=k!
No, that's incorrect for two reasons.kathrynag said:2k!=(2k)(2k-2)(2k-4)...2
Mark44 said:No, that's incorrect for two reasons.
2k! = 2*k! = 2(k * (k - 1) * (k - 2) * ... 3 * 2 * 1)
On the other hand, (2k)! = 2k * (2k - 1) * (2k - 2) * ... * 3 * 2 * 1
kathrynag said:I don't ge t it. I just multiplied the 2 in.
Induction is a mathematical proof technique used to prove statements that follow a pattern or sequence. It involves proving that a statement is true for the first case, and then showing that if it holds for any given case, it also holds for the next case. This process is repeated until the statement has been proven for all cases.
The purpose of proving 2n-1<n by induction is to show that the inequality holds for all values of n, not just for a specific value. This allows us to make generalizations about the relationship between 2n-1 and n and use it in other mathematical proofs.
The steps for proving 2n-1<n by induction are as follows:
Showing that the statement is true for the first case is important because it serves as the base case for the induction proof. Without proving the base case, we cannot use the inductive step to show that the statement is true for all cases.
Some common mistakes to avoid when proving 2n-1<n by induction include: