数学の命題示しました

主に組合せ論について,読んだ本で出てきたことや,考えたことを書きます.

二乗和の公式の導出

みなさん御存知の通り,
 \displaystyle\sum_{k=1}^nk^2=\frac{1}{6}n(n+1)(2n+1)
です.

この式の導出は「 (k+1)^3-k^3=3k^2+3k+1」を k=1から k=nまで足すみたいなやつが有名です.(ググればたぶん一番上に出てきます.)
だけど,二乗和を求めると言われたときに「 (k+1)^3-k^3=3k^2+3k+1」を使う発想に至るのは飛躍が大きい気がして個人的にあまり好きじゃないです.

この記事では,母関数を使った導出方法を紹介します.
数列「 1,2^2,3^2,\ldots,n^2」の母関数は
 1+2^2q+3^2q^2+\cdots+n^2q^{n-1}」です.
この母関数を計算して q\to 1の極限を取れば,二乗和の公式が得られます.
母関数の世界では,数列「 (a_k)_{k=1}^n」を「 (ka_k)_{k=1}^n」に変えるのは
母関数を q微分して qをかける操作に対応します.今回は二乗和なのでそれを二回やります.

命題 (二乗和の公式)

 \displaystyle\sum_{k=1}^nk^2=\frac{1}{6}n(n+1)(2n+1)

証明

まず,
 \displaystyle \sum_{k=0}^nq^k= \frac{1-q^{n+1}}{1-q}
です.
両辺を q微分します.
 \displaystyle \sum_{k=0}^nkq^{k-1}= \frac{nq^{n+1}-(n+1)q^n+1}{(1-q)^2}
両辺に qをかけます.
 \displaystyle \sum_{k=0}^nkq^{k}= \frac{nq^{n+2}-(n+1)q^{n+1}+q}{(1-q)^2}

両辺をまた q微分します.
  \displaystyle \sum_{k=0}^n k^2q^{k-1} = \frac{-n^2q^{n+2}+(2n^2+2n-1)q^{n+1}-(n+1)^2q^n+q+1}{(1-q)^3}

極限 q\to 1をとります.左辺は \sum_{k=0}^nk^2になり,右辺はロピタルの定理を使います.(分母と分子を別々に三回微分したやつに q=1を入れます.)
すると,
 \displaystyle\sum_{k=1}^nk^2=\frac{1}{6}n(n+1)(2n+1)
を得ます.(証明終わり)