読者です 読者をやめる 読者になる 読者になる

プログラミングする数学信者

数学信者が数学とプログラミングの話題を中心にして何か書きます

二項係数に関する恒等式

数学

この恒等式を証明します。
\displaystyle \sum_{j=1}^{n} j\binom{2n}{n+j} = \frac{n}{2} \binom{2n}{n} \tag{*} \label{eq0}
元ネタはhttps://twitter.com/MERU9RIN/status/684313920945786880です。


証明に必要な公式はこの3つです。
\begin{align} 
j \binom{n}{j} &= n \binom{n-1}{j-1} \tag{1} \\
2\sum_{j=1}^n \binom{2n}{n+j} &= 2^{n} - \binom{2n}{n} \tag{2} \\
2\sum_{j=1}^n \binom{2n-1}{n+j-1} &= 2^{n-1} \tag{3}
\end{align}

1つ目は二項係数の定義よりわかります。
残りの2つは、\sum_{j=0}^{n} \binom{n}{j} = 2^{n}\binom{n}{j} = \binom{n}{n-j} を使うと導き出せます。

上で挙げた3つの公式を用いると、恒等式の証明は次のようにできます。
\begin{align}
& \sum_{j=1}^{n} j\binom{2n}{n+j} \\
= & \sum_{j=1}^{n} (n+j) \binom{2n}{n+j} - n \sum_{j=1}^{n} \binom{2n}{n+j} \\
= & 2n \sum_{j=1}^{n} \binom{2n-1}{n+j-1} - n \sum_{j=1}^{n} \binom{2n}{n+j} \\
= & n 2^{n-1} - n \left( 2^{n-1} - \frac{1}{2} \binom{2n}{n} \right) \\
= & \frac{n}{2} \binom{2n}{n}
\end{align}

P.S. もし組み合わせ論的に恒等式\eqref{eq0}を証明できる人がいたら、証明を教えて下さい。