このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

[定理]n!~=~\sum_{k=0}^{n}~(-1)^k~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~(a-k)^n

[補講]この式の左辺は、aに無関係であることに注目。 ◇

[証明](数学的帰納法による証明)

[1]nの場合は成り立つと仮定する。

[2]nをn+1で置き換えた結果である次の内容が成り立つことを証明する。

(n+1)!~=~\sum_{k=0}^{n+1}~(-1)^k~\left(\begin{matrix}n+1~\\~k~\\\end{matrix}\right)~(a-k)^{n+1}

(右辺)
=\sum_{k=0}^{n+1}~(-1)^k~\left(\begin{matrix}n+1~\\~k~\\\end{matrix}\right)~(a-k)^{n+1} (∵Σをk=0とk=1〜nとk=n+1のところで分解する)
=a^{n+1}~+~\sum_{k=1}^{n}~(-1)^k~\left(\begin{matrix}n+1~\\~k~\\\end{matrix}\right)~(a-k)^{n+1}~+~(-1)^{n+1}(a-n-1)^{n+1}
=a^{n+1}~+~\sum_{k=1}^{n}~(-1)^k~(\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~(a-k)^{n+1}~+~\left(\begin{matrix}n~\\~k-1~\\\end{matrix}\right)~(a-k)^{n+1})~+~(-1)^{n+1}(a-n-1)^{n+1} (∵\left(\begin{matrix}n+1~\\~k~\\\end{matrix}\right)~=~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~+~\left(\begin{matrix}n~\\~k-1~\\\end{matrix}\right)、ただし、0<k≦n)
=a^{n+1}~+~\sum_{k=1}^{n}~(-1)^k~(\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~a(a-k)^n~-~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~k(a-k)^n~+~\left(\begin{matrix}n~\\~k-1~\\\end{matrix}\right)~(a-k)^{n+1})~+~(-1)^{n+1}(a-n-1)^{n+1} (∵(a-k)^{n+1}~=~(a-k)(a-k)^n
=a^{n+1}~+~\sum_{k=1}^{n}~(-1)^k~(\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~a(a-k)^n~+~(-~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~k~+~\left(\begin{matrix}n~\\~k-1~\\\end{matrix}\right)~(a-k))(a-k)^n~)~+~(-1)^{n+1}(a-n-1)^{n+1}
=a^{n+1}~+~\sum_{k=1}^{n}~(-1)^k~(\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~a(a-k)^n~+~(\frac{-n!}{(n-k)!(k-1)!}~+~\frac{n!(a-k)}{(n-k+1)!(k-1)!})~(a-k))(a-k)^n~)~+~(-1)^{n+1}(a-n-1)^{n+1} (∵組み合わせの定義より、_nC_k~=~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~=~\frac{n!}{k!(n-k)!}
=a^{n+1}~+~\sum_{k=1}^{n}~(-1)^k~(\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~a(a-k)^n~-~\frac{n!(n+1-a)}{(n-k+1)!(k-1)!}~(a-k)^n~)~+~(-1)^{n+1}(a-n-1)^{n+1} (∵\frac{-n!}{(n-k)!(k-1)!}~+~\frac{n!(a-k)}{(n-k+1)!(k-1)!}=-\frac{n!}{(k-1)!}(\frac{1}{(n-k)!}-\frac{a-k}{(n-k+1)!})=-\frac{n!}{(k-1)!}(\frac{n-k+1}{(n-k+1)!}-\frac{a-k}{(n-k+1)!})~=~-\frac{n!}{(n-k+1)!(k-1)!}((n-k+1)-(a-k))~=~-\frac{n!}{(n-k+1)!(k-1)!}(n-a+1)~=~-\frac{n!(n-a+1)}{(n-k+1)!(k-1)!}
=a^{n+1}~+~\sum_{k=1}^{n}~(-1)^k~(\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~a(a-k)^n~-~(n+1-a)~\left(\begin{matrix}n~\\~k-1~\\\end{matrix}\right)~(a-k)^n~)~+~(-1)^{n+1}(a-n-1)^{n+1} (∵\frac{n!}{(k-1)!(n-k+1)!}=\left(\begin{matrix}n~\\~k-1~\\\end{matrix}\right)
=a^{n+1}~+~\sum_{k=1}^{n}~(-1)^k~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~a(a-k)^n~-~\sum_{k=1}^{n}~(-1)^k~(n+1-a)~\left(\begin{matrix}n~\\~k-1~\\\end{matrix}\right)~(a-k)^n~~+~(-1)^{n+1}(a-n-1)^{n+1} (∵Σの括弧を外す)
=a^{n+1}~+~a\sum_{k=1}^{n}~(-1)^k~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~(a-k)^n~-~(n+1-a)~\sum_{k=1}^{n}~(-1)^k~\left(\begin{matrix}n~\\~k-1~\\\end{matrix}\right)~(a-k)^n~~+~(-1)^{n+1}(a-n-1)^{n+1} (∵Σ内において、kに関係ないところを外出しする)
=a^{n+1}~+~a\sum_{k=1}^{n}~(-1)^k~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~(a-k)^n~+~(n+1-a)~\sum_{k=1}^{n}~(-1)^{k-1}~\left(\begin{matrix}n~\\~k-1~\\\end{matrix}\right)~(a-k)^n~~+~(-1)^{n+1}(a-n-1)^{n+1} (∵(-1)\sum_{k=1}^{n}~(-1)^{k}~=~\sum_{k=1}^{n}~(-1)^{k-1}
=an!~+~(n+1-a)~\sum_{k=1}^{n}~(-1)^{k-1}~\left(\begin{matrix}n~\\~k-1~\\\end{matrix}\right)~(a-k)^n~~+~(-1)^{n+1}(a-n-1)^{n+1} (∵仮定より、a^{n+1}~+~a\sum_{k=1}^{n}~(-1)^k~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~(a-k)^n~=~a\sum_{k=0}^{n}~(-1)^k~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~(a-k)^n=an!
=an!~+~(n+1-a)~[\sum_{k=0}^{n-1}~(-1)^{k}~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~(a-k-1)^n~~+~(-1)^{n}(a-n-1)^{n}] (∵k-1をkとした)
=an!~+~(n+1-a)~\sum_{k=0}^{n}~(-1)^{k}~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~(a-k-1)^n (∵仮定において、aをa-1とした結果を使用する)
=an!~+~(n+1-a)n! (∵仮定より)
=(n+1)! (∵an!~+~(n+1-a)n!=n!(a-(n+1-1))=n!(n+1)=(n+1)!
=(左辺)

したがって、数学的帰納法より、題意が成り立つ。 □