求证：当且仅当n为2的幂时，(2n-1)!/(n!(n-1)!)为奇数

咱们接着你已经完成的充分性证明，来搞定必要性：当$\frac{(2n-1)!}{n! (n-1)!}$是奇数时，$n$必须是2的幂，或者等价地证明：若$n$不是2的幂，则该式必为偶数。

核心工具：Legendre公式的二进制推论 #

我们用Legendre公式中关于2的指数的一个实用结论：对于任意正整数$m$，$m!$中含2的最高次幂为$v_2(m!) = m - s_2(m)$，其中$s_2(m)$是$m$的二进制表示中1的个数。这个结论你已经用到过（比如$2^{r!$中2的指数是$2}r -1$，因为$s_2(2^r)=1$）。

计算目标式的2的指数 #

我们需要计算：
$$
v_2\left( \frac{(2n-1)!}{n! (n-1)!} \right) = v_2((2n-1)!) - v_2(n!) - v_2((n-1)!)
$$

代入上面的结论：
$$
\begin{align*}
v_2((2n-1)!) &= (2n-1) - s_2(2n-1) \
v_2(n!) &= n - s_2(n) \
v_2((n-1)!) &= (n-1) - s_2(n-1)
\end{align*}
$$

把这三个式子相减，化简后常数项抵消，得到：
$$
v_2\left( \frac{(2n-1)!}{n! (n-1)!} \right) = s_2(n) + s_2(n-1) - s_2(2n-1)
$$

用二进制进位分析差值 #

这里用到二进制加法的一个关键性质：两个整数$a,b$相加时，二进制的进位次数$t$满足$s_2(a) + s_2(b) = s_2(a+b) + t$（每进位一次，二进制中会减少1个1，所以总和的1的个数等于两个数1的个数之和减去进位次数）。

令$a=n$，$b=n-1$，则$a+b=2n-1$，代入性质得：
$$
s_2(n) + s_2(n-1) = s_2(2n-1) + t
$$

其中$t$是$n$与$n-1$相加时的进位次数。把这个代入之前的指数表达式，得到：
$$
v_2\left( \frac{(2n-1)!}{n! (n-1)!} \right) = t
$$

关键结论推导 #

• 当$n$是2的幂时，$n$的二进制是100...0，$n-1$的二进制是011...1，两者相加时每一位都是1+0或0+1，没有进位（$t=0$），因此$v_2=0$，式子是奇数（这就是你已经证明的充分性）。
• 当$n$不是2的幂时，$n$的二进制中至少有两个1，此时$n$与$n-1$相加时至少有一次进位（比如最右边的1和$n-1$中对应的位相加会引发进位链），即$t≥1$，因此$v_2≥1$，式子必为偶数。

反过来，如果式子是奇数，说明$v_2=0$，即$t=0$，这只有$n$是2的幂时才成立，必要性得证。

内容的提问来源于stack exchange，提问作者Muhammad Rasel Parvej