Hard mathematical induction question

[ZOMGbirdy]

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.

 

[Simon Bridge]

(k+1)(k+2)(k+3)...(2k-1)2k = 2^k[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
f₁f₂f₃...f_m=P_m(k)

where
f_i = k+i

but for i=m, f_m = k+m = 2k(2k-1)
so what is f_m-1 ?

 

[ZOMGbirdy]

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.

 

[Simon Bridge]

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 :)

 

[alphy]

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