danza108 said:
I was wondering if anyone could help me out here, its from the RUse 2005 Extenion 1 paper. q5 I think.
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 can show the first part, the divisiblity, how about the not true part. Is it two inductions, or contradiction, or what? Thanks a lot for any help.
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)
n=1: (1+1)=2, 2^1=2
2^1 is a multiple of 2
n=2: (2+1)(2+2)=12, 2^(3)=8
2^3 is clearly not a multiple of 12
So the statement is true for n between 1 and 2
Assume the statement is true for n=k,
i.e: (k+1)(k+2)...(k+k) is a multiple of 2^k---->(1)
and also: (k+1)(k+2)...(k+k) is not a multiple of 2^(k+1)--->(2)
Now prove the statement is true for n=k+1, i.e:
(k+2)(k+3)...(k+k)(k+1+k+1) is a multiple of 2^(k+1) but not a multiple of 2^(k+2)
Using (1):
(k+1)(k+2)...(k+k)=(2^k)m where m integral
(k+2)(k+3)...(k+k)(k+1+k+1)=(2^k)m(k+1+k+1)\(k+1)
... same thing....=m(2^k)2(k+1)\(k+1)
(k+2)(k+3)...(k+k)(k+1+k+1)=m[2^(k+1)]---->(3)
.: (k+2)(k+3)...(k+k)(k+1+k+1) is a multiple of 2^(k+1)
Assume (k+2)(k+3)...(k+k)(k+1+k+1) IS multiple of 2^(k+2)
(k+2)(k+3)...(k+k)(k+1+k+1)=m[2^(k+2)]
(k+1)(k+2)....(k+k)=m[2^(k+2)](k+1)\(k+1+k+1)
... same thing...=m[2^(k+2)](k+1)\2(k+1)
...same thing...=m[2^(k+1)]
but from (2):
(k+1)(k+2)...(k+k) is not a multiple of 2^(k+1)
.: it is wrong to assume (k+2)(k+3)...(k+k)(k+1+k+1) IS multiple of 2^(k+2)
.: (k+2)(k+3)...(k+k)(k+1+k+1) is NOT a multiple of 2^(k+2) as required
Hope that's correct LoL
