combinatorial proof of $2^{n+1}\nmid (n+1)(n+2)\dots (2n)$ combinatorial proof of $2^{n+1}\nmid (n+1)(n+2)\dots (2n)$.
I don't have any ideas about proving $sth \nmid sthx$ using combinatorics for showing $sth \mid sthx$ we show that there is a problem that gives $\frac{sthx}{sth*k}$ but what about proving sth doesn't divide sth using combinatorics?
 A: Hint:
If $$p_n:=(n+1)(n+2)\cdots(2n)$$ then $$p_{n+1}=p_n(2n+1)2$$ so it has exactly one factor $2$ more than $p_n$
A: You want to establish that the highest possible power of 2 in the prime factorisation of (n+1)...(2n) is $2^n$.
On the left hand side you have n consecutive factors from n+1 to 2n. How many even numbers are there is these n factors ? There must be n/2 - so there is at least a factor of $2^{n/2}$ in the prime factorisation of (n+1)...(2n).
Now how many multiples of 4 are there from n+1 to 2n ? Well it depends on n, but let's take a "worst case" scenario - what is the maximum number of multiples of 4 from n+1 to 2n ? Each multiple of 4 increases the power of 2 in the prime factorisation of (n+1)...(2n) by 1.
Now carry on looking at multiples of 8, 16, 32 etc. The index of 2 increase each time, but by smaller and smaller amounts. Eventually you will reach a point where there are no more powers of 2 from n+1 to 2n - but, again, take a worst case scenario and assume n is really really large.
Can you see why the index of 2 in the prime factorisation of (n+1)...(2n) can never exceed n ?
