私的数学日誌

読者提供

「yuyusama提供：二項係数と2の冪乗の関係式」

ありがたいことに話題を提供してくださる読者がいらしたので、その方の話題を取り扱おう。

今回証明する恒等式は次の式である。

nCk ・2^(n-k)=Σ(i=0→n-k) nC(k+i) (k+i)Ck (n≧k、n,kは非負の整数)

[証明]

左辺から右辺に持っていくのはなかなか難しそうなので、右辺から左辺に持っていこう。

二項係数の階乗による表示（nCk=n!/k!(n-k)!）によると、Σ(i=0→n-k) nC(k+i) (k+i)Ck=Σ(i=0→n-k) n!/(n-k-i)!k!i! =n!/k! ・Σ(i=0→n-k)1/(n-k-i)!i!

ここで、シグマの中に入っている階乗の項に注目してみると、これは(n-k)Ci の階乗表示の分母になっていることがわかる。つまり、次のように変形できる。

(与式)=n!/(n-k)!k! ・Σ(i=0→n-k)(n-k)!/(n-k-i)!i!=nCk ・ Σ(i=0→n-k) (n-k)Ci

Σ(i=0→n) (n-k)Ciは二項係数の関係式で2^(n-k)と等しくなることを示したから、

(与式)=nCk ・ 2^(n-k)

このように、二項係数の公式は代数的な方法で簡単に導ける場合がある。