How did my colleague conclude on equation (ii)?

In summary, the conversation is about proving that ##(n+1)!≥ 2^n. n## when ## n≥3## using mathematical induction. The colleague suggests that the equation in question should be ##(k+2)!≥ 2^{k+1} (k+1)##. They then provide a proof using the inductive assumption. The other person suggests a neater way to prove it by stating that ##k(k+2) > 2(k+1)## for all ##k \geq 3## and showing that this leads to the desired inequality.
  • #1
chwala
Gold Member
2,571
343
Homework Statement
prove that,

##(n+1)!≥ 2^n. n## when ## n≥3##
Relevant Equations
mathematics induction
1599832781653.png

this is a solution posted by my colleague, i have a problem in understanding how he got to conclude on equation (ii)
1599832871622.png

is this not supposed to be ##(k+2)!≥ 2^{k+1} (k+1)##
##(k+2)(k+1)!≥ 2^{k+1} (k+1)## ?...
 
Physics news on Phys.org
  • #2
Assume that ##(k+1)! \geq 2^k k##. Then notice that ##(k+2)! = (k+2)(k+1)!##, and since ##(k+1)! \geq 2^k k## by assumption, you have ##(k+2)! = (k+2)(k+1)! \geq (k+2)2^k k##.

You're trying to show that ##(k+2)!## is greater than ##2^{k+1}(k+1)## given that it holds for the case below, so you can't assume what's meant to be proven!
 
  • #3
chwala said:
Homework Statement:: prove that,

##(n+1)!≥ 2^n. n## when ## n≥3##
Relevant Equations:: mathematics induction

View attachment 269193
this is a solution posted by my colleague, i have a problem in understanding how he got to conclude on equation (ii)
View attachment 269194
is this not supposed to be ##(k+2)!≥ 2^{k+1} (k+1)##
##(k+2)(k+1)!≥ 2^{k+1} (k+1)## ?...
The inductive assumption is that ##(k+1)!≥ 2^{k} (k)##, hence:
$$(k+2)! = (k+2)(k+1)! \ge (k+2)2^k (k)$$
 
  • Like
Likes chwala
  • #4
aaaaaaah i have seen it...
 
  • Like
Likes etotheipi
  • #5
There must be a neater way to do this. That proof you attached is quite laboured.
 
  • #6
PeroK said:
There must be a neater way to do this. That proof you attached is quite laboured.

you mind showing a neater way now that i am conversant with how the solution was found...
 
  • #7
You just need to state that ##k(k+2) > 2(k+1)## for all ##k \geq 3##. Then it follows that$$(k+2)! \geq k(k+2)2^k > 2(k+1) 2^k = (k+1)2^{k+1}$$
 
  • Like
Likes chwala and PeroK
  • #8
For the inductive step, all that is required is:
$$(k+2)! = (k+2)(k+1)! \ge (k+2)2^k(k) > (k+1)2^{k+1} \ \ \ (\text{as} \ k + 2 > k+1 \ \text{and} \ k > 2)$$
 
  • Like
Likes chwala and etotheipi

1. What is the concept of proof by induction?

Proof by induction is a mathematical technique used to prove that a statement or formula is true for all natural numbers. It involves breaking down the problem into smaller cases and proving that each case leads to the next, until the entire statement is proven true.

2. How is proof by induction different from other proof techniques?

Proof by induction is different from other proof techniques because it relies on the principle of mathematical induction, which states that if a statement is true for a particular value, and also true for the next value, then it is true for all values after that. This allows for a more efficient and systematic approach to proving statements.

3. When should proof by induction be used?

Proof by induction should be used when trying to prove a statement or formula that involves natural numbers, such as equations involving factorials or sums. It is particularly useful when the statement involves a pattern that can be broken down into smaller cases.

4. What are the steps involved in a proof by induction?

The steps involved in a proof by induction are as follows:

  1. Base case: Prove that the statement is true for the first value (usually n = 1).
  2. Inductive hypothesis: Assume that the statement is true for some arbitrary value k.
  3. Inductive step: Use the inductive hypothesis to prove that the statement is true for the next value (k+1).
  4. Conclusion: Since the statement is true for n=1 and the inductive step shows that it is true for n=k+1, it is true for all natural numbers.

5. What are some common mistakes to avoid when using proof by induction?

Some common mistakes to avoid when using proof by induction include:

  • Not proving the base case or assuming it is true without proof.
  • Assuming the inductive hypothesis is true for all values instead of just the next value.
  • Using circular reasoning by assuming the statement is true in the inductive step.
  • Not clearly stating the inductive hypothesis and inductive step.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
975
  • Calculus and Beyond Homework Help
Replies
3
Views
429
  • Calculus and Beyond Homework Help
Replies
6
Views
716
  • Calculus and Beyond Homework Help
Replies
5
Views
419
  • Calculus and Beyond Homework Help
Replies
2
Views
454
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
965
  • Calculus and Beyond Homework Help
Replies
4
Views
931
  • Calculus and Beyond Homework Help
Replies
6
Views
398
  • Calculus and Beyond Homework Help
Replies
2
Views
521
Back
Top