disproof by induction (1 Viewer)

[5647382910]

I can do the first part (the proof) but not the second (the disproof):
Prove by induction that, for any positive integer n, the product (n + 1)(n + 2)....(n + n) is always a multiple of 2^n but never a multiple of 2^(n + 1)

I tried by proving that its not true for n = 1, then assuming not true for n = k and trying to show that it is not true for n = k + 1, but i couldnt do that.

thanks in advance

 

[tommykins]

I believe you're meant to assume true for n = k but trynig to prove true for n = k+1 fails hence the statement is incorrect.

 

[5647382910]

I believe you're meant to assume true for n = k but trynig to prove true for n = k+1 fails hence the statement is incorrect.

yes, but:
1. were saying that it is true for a value, when we are meant to prove it isnt for any
2. we are saying that it isnt true for the value following the value it is true for, so for it to be not true, the one before has to be true; imm not sure how to explain it, but the 'domino effect' doesnt work in doing this

 

[Trebla]

Here's my take on it....

For n = 1,
LHS = 2
RHS = 4
LHS =/= RHS, so the statement is not true for n = 1
Assume the statement is true for n = k
(k + 1)(k + 2)....(k + k) = 2^{k + 1}.M (for some integer M)
Need to prove it is true for n = k + 1
(k + 2)(k + 3)....(k + 1 + k + 1) = 2^{k + 2}.N (for some integer N)
LHS = (k + 2)(k + 3)....(k + k)(k + 1 + k + 1)
= 2(k + 1)(k + 2)(k + 3)....(k + k)
= 2.2^{k + 1}.M using the assumption
= 2^{k + 2}.M
= 2^{k + 2}.N (N = M which is an integer)
= RHS
Since we've used the assumption, the statement is ONLY true for n = k + 1 IF OUR ASSUMPTION IS TRUE for n = k. (i.e. the next number cannot be proved to satisfy the statement unless the number before it is deemed to satisfy the statement)
BUT we know without assumption that it is NOT true for n = 1. So n = 1 + 1 = 2 is not true either (because it is only true if n = 1 is true) and similarly n = 2 + 1 = 3 is not true. Hence the statement is false because we have no initial case to verify the validity of the assumption.

You go nowhere if you assume the statement is false for n = k, because the n = k + 1 case cannot be used in argument at all if that happens. Similarly, you cannot disprove it for n = k + 1, after assuming n = k is assumed true because you have no "domino effect" to use to disprove for all positive integers of n. You must prove it is true for n = k + 1 if the assumption is true, to be able to utilise the generalisation over all positive integers of n. In the approach above, if the assumption breaks down, then all n = k + 1 (proven to be true if the assumption holds) also breaks down.