和分法とスターリング数
はじめに
Mathlogの 高校数学の数列と微分積分は似ているという話（和分差分） を拝見し、自分も同じようなことをはてブロにかいたこと思い出したので、それを再構成してみました。厳密なものではないのでその点はご承知ください。
和分法とは？
関数を積分すると、ある区間の面積や体積などを求めることができる。例えば、関数 $f(x)=x^{2}$の $[0,n]$ 区間の面積を求めるときは、以下の定積分を計算するだけである。
\begin{align} \int_{0}^{n} x^{2}dx = \left[\frac{1}{3}x^{3} \right]_0^n=\frac{1}{3}n^3 \end{align}
これと同じように数列でも簡単に部分和を求めることができる方法がある。それが和分法であり、積分法の離散バージョンと考えて良い。例えば、数列 $f(n)=n^2-n$ の部分和 $S_n$ は以下のように定積分と同じ要領で求められる。
\begin{align} S_n &= \sum_{x=0}^n (x^2-x) \\ &= \sum_{0\leq x< n+1} (x^2-x) \\ &= \sum \ _{0}^{n+1} (x^2-x) \delta x\\ &= \sum \ _{0}^{n+1} x(x-1) \delta x\\ &= \sum \ _{0}^{n+1} x^{\underline{2}} \delta x\\ &= \left[\frac{1}{3}x^{\underline{3}}\right]_0^{n+1}\\ &= \frac{1}{3}(n+1)^{\underline{3}}-0^{\underline{3}}\\ &=\frac{1}{3}(n+1)n(n-1)\\ &=\frac{n^3-n}{3} \end{align}
これは Wolfram Alphaで求めた結果 と一致している。
和分記号 $\sum_{0}^{n+1}$ は積分記号 $\int_{0}^{n+1}$ と対応している。少し見にくいが、数式の4,5,6行目のべき乗の数字には下線がついている。これは 下降階乗 であり、以下のように定義されている。
\begin{align} x^{\underline{n}} &= \frac{x!}{(x-n)!}\\ &=\begin{cases} x(x-1)\cdots (x-n+1)\quad (n \geq 0)\\ \displaystyle \frac{1}{(x+1)(x+2)\cdots (x-n)}\quad (n < 0) \end{cases} \end{align}
$n$ が正のとき、これは 順列$\ _xP_n$ と同じになる。下降階乗は離散系の和差演算において重要な性質を持っている。
下降階乗の性質
微分では、以下が成り立っていた。
$n\neq 0$のとき、
\begin{align}
\frac{d}{dx} x^n = nx^{n-1}
\end{align}
この性質により、積分は以下のように計算できる。
$n\neq -1$のとき、
\begin{align}
\int x^ndx = \frac{1}{n+1}x^{n+1} + \mathrm{const}
\end{align}
離散系でこの性質が成り立つのが先程導入した下降階乗である。微分に対応する演算として差分を以下のように定義する。
$\Delta f(x) = f(x+1)-f(x)$
差分に関して以下のことが成り立つ。
$n\neq 0$のとき、
\begin{align}
\Delta x^{\underline{n}} &= (x+1)^{\underline{n}} - x^{\underline{n}} \\
&= (x+1)x(x-1)\cdots (x-n+2)- x(x-1)\cdots (x-n+1)\\
&= \{(x+1)-(x-n+1)\}x(x-1)\cdots (x-n+2)\\
&=nx^{\underline{n-1}}
\end{align}
負の数に対してもこの性質は成り立つ。この性質を使って、積分に対応する演算である和分は以下のように考えることができる。
$n\neq -1$のとき、
\begin{align}
\sum x^{\underline{n}}\delta x = \frac{1}{n+1}x^{\underline{n+1}} + \mathrm{const}
\end{align}
和分と積分の対応
以上のことを一般化すると、次の対応表が得られる。
| 微分 | 積分 | |
|---|---|---|
| 連続系 | $f(x)=\frac{d}{dx}F(x)]$ | $\int f(x)dx = F(x) + \mathrm{const}$ |
| 離散系 | $f(x)=\Delta F(x)$ | $\sum f(x)\delta x = F(x) + \mathrm{const}$ |
また、定和分については以下が成り立つ。
\begin{align} \sum_{a\leq x < b} f(x) &= \sum_{a\leq x < b} \Delta F(x)\\ &=\sum_{a\leq x < b}\{F(x+1)-F(x)\}\\ &= \{F(b)-F(b-1)\}+\{F(b-1)-F(b-2)\}+\cdots \\ &\quad + \{F(a+2)−F(a+1)\} + \{F(a+1)−F(a)\}\\ &= F(b)-F(a)\\ &= \sum \ _a^b f(x)\delta x \end{align}
以上が先程の数列の部分和が定和分で求められる理由である。和分法ではこれ以外にも多くの数列の部分和を求めることができる。
いろいろな関数の和分と差分
下降階乗の例外
下降階乗についての性質は、連続系と同じように $n=-1$ では例外となる。 $n=-1$ では次の 調和数 となる。
\begin{align} H_x = \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{x} \end{align}
これは、以下のように確かめることができる。
\begin{align} \Delta H_x &= H_{x+1}-H_x\\ &= \left\{\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{x} + \frac{1}{x+1}\right\} - \left\{\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{x}\right\}\\ &= \frac{1}{x+1}\\ &= x^{\underline{-1}}\\ \end{align}
指数関数
$f(x) = a^x$ に対して、差分をとると以下のようになる。
\begin{align} \Delta f(x) &= f(x+1) - f(x)\\ &= a^{x+1} - a^x\\ &= (a-1)a^x\\ \end{align}
これは $a$ が負の値を持つ場合にも有効である。また、$a = 2$ のとき、
\begin{align} \Delta f(x) &= (2-1)a^x\\ &= a^x\\ &= f(x) \end{align}
となり、差分が元の関数と一致する。これは連続系の $e^x$ に対応している。
部分和分
連続系の部分積分のように、離散系での部分和分を考える
\begin{align} \Delta(f(x)g(x)) &= f(x+1)g(x+1) - f(x)g(x)\\ &= f(x+1)g(x+1) - f(x)g(x+1) + f(x)g(x+1) - f(x)g(x)\\ &= \{f(x+1)g(x+1) - f(x)g(x+1)\} + \{f(x)g(x+1) - f(x)g(x)\}\\ &= (f(x+1)-f(x))g(x+1) + f(x)(g(x+1)-g(x))\\ &=\Delta f(x) g(x+1) + f(x)\Delta g(x) \end{align}
これを移項して和分すると、部分和分が得られる。
\begin{align} \sum f(x)\Delta g(x) \delta x = f(x)g(x) - \sum g(x+1)\Delta f(x) \delta x \end{align}
具体例
以上のことを使って和を求めてみる。
\begin{align} \sum_{k=0}^n k3^k &= \sum \ _0^{n+1} x3^x \delta x\\ &=\sum \ _0^{n+1} x\frac{3-1}{3-1}3^x \delta x\\ &= \frac{1}{3-1}\sum \ _0^{n+1} x(3-1)3^x \delta x\\ &= \frac{1}{2} \sum \ _0^{n+1} x \Delta(3^x) \delta x\\ &= \frac{1}{2}\left\{ [x3^x]_0^{n+1}-\sum \ _0^{n+1} 3^{x+1}\Delta x\delta x \right\}\\ &= \frac{1}{2}\left\{ [x3^x]_0^{n+1}-\sum \ _0^{n+1} 3^{x+1}((x+1)-x)\delta x \right\}\\ &= \frac{1}{2}\left\{ [x3^x]_0^{n+1}-\sum \ _0^{n+1} 3^{x+1}\delta x \right\}\\ &= \frac{1}{2}\left\{ \left[x3^x\right]_0^{n+1}-\left[\frac{1}{3-1} 3^{x+1} \right]_0^{n+1}\right\}\\ &= \frac{1}{2}\left\{ \left[x3^x\right]_0^{n+1}-\left[\frac{1}{2} 3^{x+1} \right]_0^{n+1}\right\}\\ &= \frac{1}{2}\left\{ \left[x3^x\right]_0^{n+1}-\left[\frac{3}{2} 3^{x} \right]_0^{n+1}\right\}\\ &= \frac{1}{2}\left[\left(x-\frac{3}{2}\right)3^x\right]_0^{n+1}\\ &=\frac{1}{2}\left\{\left(n+1-\frac{3}{2}\right)3^{n+1}-\left(0-\frac{3}{2}\right)3^0\right\}\\ &=\frac{1}{2}\left\{\left(n-\frac{1}{2}\right)3^{n+1}+\frac{3}{2}\right\}\\ &= \frac{n3^{n+1}}{2}-\frac{3^{n+1}}{4}+\frac{3}{4} \end{align}
Wolfram Alphaで確認してみると 一致していることがわかる。
\begin{align} \sum_{k=0}^n H_k &= \sum \ _0^{n+1} H_x \delta x\\ &= \sum \ _0^{n+1} H_x\cdot 1 \delta x\\ &= \sum \ _0^{n+1} H_x\cdot \Delta x^{\underline{1}} \delta x\\ &= [xH_x]_0^{n+1}- \sum \ _0^{n+1} (x+1)^{\underline{1}} \Delta H_x \delta x\\ &= [xH_x]_0^{n+1} - \sum \ _0^{n+1} (x+1)^{\underline{1}} x^{\underline{-1}}\delta x\\ &= [xH_x]_0^{n+1} - \sum \ _0^{n+1} \frac{x+1}{x+1}\delta x\\ &= [xH_x]_0^{n+1} - \sum \ _0^{n+1} \delta x\\ &= [xH_x]_0^{n+1} -[x^{\underline{1}}]_0^{n+1}\\ &= [xH_x]_0^{n+1} -[x]_0^{n+1}\\ &= [xH_x-x]_0^{n+1}\\ &= [x(H_x-1)]_0^{n+1}\\ &= (n+1)(H_{n+1}-1) \end{align}
Wolfram Alphaで確認してみると 一致していることがわかる。
和分法を用いると複雑な部分和を計算だけで求めることができる。以下の和も和分法で求められる例である。
\begin{gather}
\sum_{k=0}^n k(-1)^k\\
\sum_{k=0}^n \frac{H_k}{(k+1)(k+2)(k+3)}
\end{gather}
下降階乗ではない多項式の和分
任意の多項式は下降階乗のみを用いた式に表せることが知られている。下降階乗のみの式に変換してから和分法を適用すれば良い。この変換には、スターリング数を使う。
スターリング数とは？
スターリング数の定義に関しては こちらのサイト がわかりやすい。
第2種スターリング数を ${}_nS_k$ と表すこととする。第2種スターリング数の重要な性質として、以下の漸化式が成り立つことが知られている。
\begin{aligned} {}_{n}S_{k} = k\ {}_{n-1}S_{k} + {}_{n-1}S_{k-1} \end{aligned}
通常のべきと下降階乗の変換
通常のべきの場合は、第2種スターリング数を以下のように使うことで下降階乗に変換することができる。
\begin{align} x^n = \sum_{k=0}^n \ _nS_k x^{\underline{k}} \end{align}
これは数学的帰納法で証明できる。
$n=0$ のとき
\begin{align} \mbox{(右辺)} &= \sum_{k=0}^0 \ _0S_k x^{\underline{k}}\\ &= \ _0S_0 x^{\underline{0}}\\ &=1\cdot x^0\\ &= x^0\\ &=\mbox{(左辺)} \end{align}
となるので成り立つ。$n-1$ のときに成り立つと仮定する。ここで
\begin{align} x^{\underline{k+1}} &= x^{\underline{k}}(x-(k+1)+1)\\ &=x^{\underline{k}}(x-k)\\ &=x\cdot x^{\underline{k}}-kx^{\underline{k}} \end{align}
より、移項すると
\begin{align} x\cdot x^{\underline{k}} = x^{\underline{k+1}} + kx^{\underline{k}} \end{align}
が成り立つ。これを利用すると、$n$ のとき
\begin{aligned} x^{n} &= x\cdot x^{n-1}\\ &= x\sum_{k=0}^{n-1}\ _{n-1}S_k x^{\underline{k}}\\ &= \sum_{k=0}^{n-1} \ _{n-1}S_k x\cdot x^{\underline{k}}\\ &= \sum_{k=0}^{n-1} \ _{n-1}S_k(x^{\underline{k+1}} + kx^{\underline{k}})\\ &= \sum_{k=0}^{n-1} \ _{n-1}S_kx^{\underline{k+1}}+ \sum_{k=0}^{n-1} \ _{n-1}S_k kx^{\underline{k}}\\ &= \sum_{k-1=0}^{n-1} \ _{n-1}S_{k-1}x^{\underline{k}}+ \sum_{k=1}^{n} \ _{n-1}S_k kx^{\underline{k}}\\ &= \sum_{k=1}^{n} \ _{n-1}S_{k-1}x^{\underline{k}}+ \sum_{k=1}^{n} \ _{n-1}S_k kx^{\underline{k}}\\ &= \sum_{k=1}^{n} (\ _{n-1}S_{k-1}+\ _{n-1}S_k k)x^{\underline{k}}\\ &= \sum_{k=1}^{n} (k\ _{n-1}S_k+\ _{n-1}S_{k-1} )x^{\underline{k}}\\ &= \sum_{k=1}^{n} \ _{n}S_kx^{\underline{k}}\\ &= \sum_{k=0}^{n} \ _{n}S_kx^{\underline{k}} \end{aligned}
となるので、成り立っている。
和分法への応用
和分法では下降階乗の性質を使うことによって計算ができていた。第2種スターリング数使って下降階乗に変換してから和分する。例えば、以下のように計算できる。
\begin{aligned} \sum {}_a^b x^n \delta x &= \sum {}_a^b \sum_{k=0}^n \ _nS_k x^{\underline{k}} \delta x\\ &= \left[\sum_{k=0}^n \frac{ \ _nS_k}{k+1}x^{\underline{k+1}}\right]_a^b\\ &=\sum_{k=0}^n \frac{ \ _nS_k}{k+1}b^{\underline{k+1}}-\sum_{k=0}^n \frac{ \ _nS_k}{k+1}a^{\underline{k+1}}\\ &=\sum_{k=0}^n \frac{ \ _nS_k}{k+1}(b^{\underline{k+1}}-a^{\underline{k+1}}) \end{aligned}
これを組み合わせれば、任意の多項式を下降階乗のみの式にするとこができるため、任意の多項式で和分法は適用可能である。
