Hard mathematical induction question

In summary, the conversation is about proving a statement. The statement is that for all integers n greater than or equal to 1, 2n-1 is equal to 2^n[1x3x5x7...x(2n-1)]. The person is trying to do the proof, but they don't understand how to do it. They are given a hint by another person, that the LHS of the statement is the same as the RHS. They are then able to figure out the proof by assuming that the statement is true for n=1 and proving that it is true for all positive integers n by induction.
  • #1
2
0
Hi everyone, I have been trying to do this induction question... but can't seem to understand how to do it.

Prove by induction that, for all integers n is greater than or equal to 1,

(n+1)(n+2)...(2n-1)2n = 2^n[1x3x...x(2n-1)]

This is what someone else has given as the answer:

For n = 1
LHS = (1 + 1) = 2
RHS = 21 = 2
LHS=RHS hence statement is true for n = 1
Assume the statement is true for n = k
(k + 1)(k + 2)...(2k - 1)2k = 2k[1 x 3 x ... x (2k - 1)]
Required to prove statement is true for n = k + 1
(k + 2)(k + 3)...(2k + 1)(2k + 2) = 2k + 1[1 x 3 x ... x (2k + 1)]
LHS = (k + 2)(k + 3)...(2k + 1)(2k + 2)
= 2(k + 1)(k + 2)(k + 3)...2k(2k + 1)
= 2(2k + 1)2k[1 x 3 x ... x (2k - 1)] by assumption
= 2k + 1[1 x 3 x ... x (2k - 1) x (2k + 1)]
= RHS
If the statement is true for n = k, it is true for n = k + 1
Since the statement is true for n = 1, it is true for all positive integers n by induction.

I think I understand everything up until he actually makes the assumption. I don't understand the assumption and what he is actually subbing into the assumption.
 
Physics news on Phys.org
  • #2
(k+1)(k+2)(k+3)...(2k-1)2k = 2k[1x3x5...x(2k-1)] = P(k)
... assumed true. (note: you left off the power?)

(k+2)(k+3)(k+4)...(2k+1)2(k+1) = 2(k+1)[1x3x5x...x(2k+1)] = P(k+1)
... needs to be proved. Kinda suggestive isn't it?

Consider:
Is the LHS of P(k+1) the same as the LHS of P(k)/(k+1) ?

The form of the LHS of P(n) is
f1f2f3...fm=Pm(k)

where
fi = k+i

but for i=m, fm = k+m = 2k(2k-1)
so what is fm-1 ?
 
  • #3
Sorry, didn't realize the powers weren't copied properly.

Thanks for your reply, yea I get it now - I was looking at it from the wrong perspective.
 
  • #4
No worries - when you are shown example proofs, they are all so very polished and clever. What you should realize is that these are the finished proofs - that is not how they were arrived at.

Don't be frightened to play around with the statements you are asked to prove. Mess about with them - figure out how they work. Look for patterns. Ask what these statements are telling you. This part is quite untidy and inelegant but you'll learn more that way.

Have fun :)
 
  • #5


Hi there,

I can see where the confusion lies in this proof. Let me try to explain the assumption step in a bit more detail.

When we say "assume the statement is true for n = k", what we are essentially saying is that we are starting with the statement for n = k, which is:

(k+1)(k+2)...(2k-1)2k = 2^k[1x3x...x(2k-1)]

This is the statement that we are assuming to be true for our induction hypothesis. Now, we need to prove that if this statement is true for n = k, then it will also be true for n = k+1.

To do this, we need to substitute n = k+1 into our original statement and see if it holds true. So, let's do that:

(k+2)(k+3)...(2k+1)(2k+2) = 2^(k+1)[1x3x...x(2k+1)]

Now we can see that the only difference between this statement and our original statement for n = k is the addition of (2k+1) and (2k+2) on the left side and the exponent of 2^(k+1) on the right side.

But, if we look back at our original statement for n = k, we can see that it already has (2k+1) in the product on the left side, and the exponent on the right side is already 2^k. So, by using our assumption that the statement is true for n = k, we can substitute in the expression 2^(k+1) = 2^k * 2, and replace (2k+1) with the product (1x3x...x(2k-1)).

This gives us:

(k+2)(k+3)...(2k+1)(2k+2) = 2^(k+1)[1x3x...x(2k+1)] = 2^k * 2 * (1x3x...x(2k-1)) = 2 * (k+1)(k+2)...(2k-1)2k = 2 * LHS (by our assumption)

And since we already know that the original statement is true for n = k, we can simply substitute
 

1. What is hard mathematical induction?

Hard mathematical induction is a proof technique used to show that a statement is true for all natural numbers greater than or equal to some base case, typically 0 or 1. It is called "hard" because it requires more complex reasoning and is typically used for more challenging proofs.

2. How is hard mathematical induction different from regular mathematical induction?

Regular mathematical induction only requires showing that a statement is true for the next natural number given that it is true for the previous one. Hard mathematical induction, on the other hand, may require showing that the statement is true for multiple consecutive natural numbers or even all natural numbers greater than or equal to a certain base case. It also often involves more complex algebraic or logical manipulations.

3. When should hard mathematical induction be used?

Hard mathematical induction should be used when regular mathematical induction is not sufficient to prove a statement. This often occurs when the statement involves multiple variables or complex relationships between numbers.

4. What are the key steps in a hard mathematical induction proof?

The key steps in a hard mathematical induction proof are: (1) stating the base case(s), typically 0 or 1; (2) assuming the statement is true for some arbitrary natural number, typically denoted as k; (3) using this assumption to prove that the statement is true for the next natural number, k+1; (4) stating a general rule that connects the statement being true for k with it being true for k+1; and (5) concluding that the statement is true for all natural numbers greater than or equal to the base case.

5. What are some tips for successfully completing a hard mathematical induction proof?

Some tips for successfully completing a hard mathematical induction proof include: (1) carefully defining the base case(s); (2) clearly stating and explaining the assumption and how it leads to the next natural number; (3) using precise and concise language; (4) being organized and showing all steps in the proof; and (5) checking for any potential errors or gaps in logic.

Suggested for: Hard mathematical induction question

Replies
7
Views
2K
Replies
3
Views
173
Replies
6
Views
2K
Replies
5
Views
4K
Replies
2
Views
3K
Replies
1
Views
3K
Replies
1
Views
2K
Replies
1
Views
3K
Replies
1
Views
1K
Back
Top