４．母関数の応用～二項変換とその逆変換

前へ　戻る

 二項変換と逆変換

ここまで母関数を一般項の導出に利用する方法を扱ってきた。この頁では数列に対する「二項変換」という操作を取り上げてみる。二項変換の内容は英語圏の一般的な解釈に準拠する。

これに対して$(-1)^k$が無いものは「二項変換の逆変換」、若しくは「逆二項変換」（inverse binomial transform）などと呼ばれるが、書籍や文献によってはいずれの変換も単に二項変換としか書いていないものもあるので注意が必要である。

不要な混乱を避けるため、この頁では前者の変換を「交代二項変換」、後者の変換を「単純二項変換」と呼称することにする。

但し、ここで定義している呼称は一般的なものではないことに注意されたい。

 二項変換の合成と母関数

（難解に感じたら例題編まで読み飛ばしても構いません）

数学的な洞察眼が優れている人は、これを一見して以下の関係に気付けるかもしれない。交代二項変換に対して、次の関係が成り立つ。

$$\small b_n=\displaystyle \sum^{n}_{k=0} (-1)^k {}_n\mathrm{C}_k a_k \iff a_n=\displaystyle \sum^{n}_{k=0} (-1)^k {}_n\mathrm{C}_k b_k \tag{2.3.0}$$

これは母関数を考えれば直ちに了解されることだろう。例えば通常型母関数の場合だと、$F(x)=\dfrac{1}{1-x}f\left(-\dfrac{x}{1-x}\right)$ であるから、

$$\small \begin{align}&\ \ \ \ \ \dfrac{1}{1-x}F\left(-\dfrac{x}{1-x}\right) \\ &=\dfrac{1}{1-x} \cdot \dfrac{1}{1+\dfrac{x}{1-x}}f\left(\dfrac{\dfrac{x}{1-x}}{1+\dfrac{x}{1-x}}\right) \\ &=\dfrac{1}{1-x+x}f\left(\dfrac{x}{1-x+x}\right) \\ &=f(x) \tag{2.3.1} \end{align} $$

となり、母関数が元に戻っている。また指数型母関数の場合だと、$G(x)=e^x g(-x)$ であるから、

$$\begin{align} e^x G(-x)&=e^x \cdot e^{-x} g(-(-x)) \\ &=g(x) \tag{2.3.3} \end{align} $$

となり、こちらでも母関数が元に戻っている。これは交代二項変換が「自己逆性」（self-inverse）を有する写像、即ち「対合」（involution）であることを意味している。式化すると以下のようになる。

$$\small \begin{align} a_n
&=\displaystyle \sum^{n}_{k=0} (-1)^k {}_n\mathrm{C}_k \displaystyle \sum^{k}_{j=0} (-1)^j {}_k\mathrm{C}_j a_j \\
&=\displaystyle \sum^{n}_{j=0} (-1)^j a_j \displaystyle \sum^{n}_{k=j} (-1)^k {}_n\mathrm{C}_k \cdot {}_k\mathrm{C}_j \\
&=\displaystyle \sum^{n}_{j=0} (-1)^j a_j \displaystyle \sum^{n}_{k=j} (-1)^k {}_n\mathrm{C}_j \cdot {}_{n-j}\mathrm{C}_{k-j} \\
&=\displaystyle \sum^{n}_{j=0} {}_n\mathrm{C}_j a_j \displaystyle \sum^{n}_{k=j} (-1)^{k+j} {}_{n-j}\mathrm{C}_{k-j} \\
&=\displaystyle \sum^{n}_{j=0} {}_n\mathrm{C}_j a_j \displaystyle \sum^{n-j}_{k=0} (-1)^k {}_{n-j}\mathrm{C}_{k} \\
&={}_n\mathrm{C}_n a_n \\
&=a_n \tag{2.3.4} \end{align} $$

なお、ここで和の交代性、及び$${}_n\mathrm{C}_k \cdot {}_k\mathrm{C}_j={}_n\mathrm{C}_j \cdot {}_{n-j}\mathrm{C}_{k-j}$$という変換公式を利用している。

単純二項変換はこのような性質を有さないが、これも母関数により容易に了解される。しかし単純二項変換に交代二項変換を組み合わせると面白い性質が見えてくる。

母関数$f(x)$に単純二項変換を施すと$$F^{*}(x)=\dfrac{1}{1-x}f\left(\dfrac{x}{1-x}\right)$$となる。これに更に交代二項変換を施してみると、

$$\small \begin{align} &\ \ \ \ \ \dfrac{1}{1-x}F^{*}\left(-\dfrac{x}{1-x}\right) \\
&=\dfrac{1}{1-x} \cdot \dfrac{1}{1+\dfrac{x}{1-x}}f\left(\dfrac{-\dfrac{x}{1-x}}{1+\dfrac{x}{1-x}}\right) \\
&=\dfrac{1}{1-x+x}f\left(-\dfrac{x}{1-x+x}\right) \\ &=f(-x) \tag{2.3.5} \end{align} $$

となる。これは式化すると以下のようになる。

$$\small \begin{align} (-1)^n a_n
&=\displaystyle \sum^{n}_{k=0} (-1)^k {}_n\mathrm{C}_k \displaystyle \sum^{k}_{j=0} {}_k\mathrm{C}_j a_j \\
&=\displaystyle \sum^{n}_{j=0} a_j \displaystyle \sum^{n}_{k=j} (-1)^k {}_n\mathrm{C}_k \cdot {}_k\mathrm{C}_j \\
&=\displaystyle \sum^{n}_{j=0} a_j \displaystyle \sum^{n}_{k=j} (-1)^k {}_n\mathrm{C}_j \cdot {}_{n-j}\mathrm{C}_{k-j} \\
&=\displaystyle \sum^{n}_{j=0} {}_n\mathrm{C}_j a_j \displaystyle \sum^{n}_{k=j} (-1)^{k} {}_{n-j}\mathrm{C}_{k-j} \\
&=\displaystyle \sum^{n}_{j=0} {}_n\mathrm{C}_j a_j \displaystyle \sum^{n-j}_{k=0} (-1)^{k-j} {}_{n-j}\mathrm{C}_{k} \\
&={}_n\mathrm{C}_n a_n (-1)^{-n} \\
&=(-1)^n a_n \tag{2.3.6} \end{align}$$

ここで $(-1)^{-n}=(-1)^n$ として計算している。

逆に、$f(x)$に交代二項変換を施してから単純二項変換を施すと、次のようになる。

$$\small \begin{align} &\ \ \ \ \ \dfrac{1}{1-x}F\left(\dfrac{x}{1-x}\right) \\ &=\dfrac{1}{1-x} \cdot \dfrac{1}{1-\dfrac{x}{1-x}}f\left(-\dfrac{-\dfrac{x}{1-x}}{1-\dfrac{x}{1-x}}\right) \\ &=\dfrac{1}{1-x-x}f\left(-\dfrac{x}{1-x-x}\right) \\ &=\dfrac{1}{1-2x}f\left(-\dfrac{x}{1-2x}\right) \tag{2.3.7}\end{align}$$

また、$f(x)$に単純二項変換を２回施すと、次のようになる。$$\small \begin{align} &\ \ \ \ \ \dfrac{1}{1-x}F^{*}\left(\dfrac{x}{1-x}\right) \\ &=\dfrac{1}{1-x} \cdot \dfrac{1}{1-\dfrac{x}{1-x}}f\left(\dfrac{-\dfrac{x}{1-x}}{1-\dfrac{x}{1-x}}\right) \\ &=\dfrac{1}{1-x-x}f\left(\dfrac{x}{1-x-x}\right) \\ &=\dfrac{1}{1-2x}f\left(\dfrac{x}{1-2x}\right) \tag{2.3.8}\end{align}$$

これらはそれぞれ以下のような母関数となっている（大きな括弧の中が被生成数列である）。

$\small \dfrac{1}{1-2x}f\left(-\dfrac{x}{1-2x}\right)=\displaystyle \sum^{\infty}_{n=0} \left(\dfrac{(-1)^n}{2^n} \displaystyle \sum^{n}_{k=0} {}_n\mathrm{C}_k a_k \right) x^n \tag{2.3.9}$

$\small \dfrac{1}{1-2x}F\left(\dfrac{x}{1-2x}\right)=\displaystyle \sum^{\infty}_{n=0} \left(\dfrac{1}{2^n} \displaystyle \sum^{n}_{k=0} {}_n\mathrm{C}_k a_k \right) x^n \tag{2.3.10}$

 二項変換に関する例題

ここまで、交代二項変換、単純二項変換という２つの数学的操作を概観してきたが、いまいち内容が分かりにくいと思われるので、簡単な例題を幾つか解いてみよう。

　《解答例》

$a_n$の母関数$f(x)$は $f(x)=\dfrac{1}{1-x}$ であるから、数列$\{b_n\}$の母関数$F(x)$は$$\small \begin{align}&\ \ \ \ \ F(x) \\ &=\dfrac{1}{1-x}f\left(-\dfrac{x}{1-x}\right) \\ &=\dfrac{1}{1-x} \cdot \dfrac{1}{1+\dfrac{x}{1-x}} \\ &= 1 \end{align}$$となる。故に数列$\{b_n\}$は$$\small \color{red}{b_0=1、b_n=0 \ (n=1,2,3,\cdots)}$$である。

また、数列$\{b^{*}_n\}$の母関数$F^{*}(x)$は$$\small \begin{align}&\ \ \ \ \ F^{*}(x) \\ &=\dfrac{1}{1-x}f\left(\dfrac{x}{1-x}\right) \\ &=\dfrac{1}{1-x} \cdot \dfrac{1}{1-\dfrac{x}{1-x}} \\ &= \dfrac{1}{1-2x} \end{align}$$となる。故に数列$\{b^{*}_n\}$は$$\small \color{red}{b^{*}_n=2^n \ (n=0,1,2,\cdots)}$$である。

これらの結果が正しいことを示そう。証明には二項係数の母関数$(1+x)^n$を用いる。

$b_n=\displaystyle \sum^{n}_{k=0} (-1)^k {}_n\mathrm{C}_k \cdot 1$ であるから、$a_n=1 \ (n=0,1,2,\cdots)$ のとき数列$\{b_n\}$は $(1+x)^n$ に $x=-1$ を代入して得られる。よって $b_n=\begin{cases} 1 \ \ \ (n=0) \\ 0 \ \ \ (n \geqq 1) \end{cases}$ となるから母関数により正しく求められていることが分かる。

また、$b^{*}_n=\displaystyle \sum^{n}_{k=0} {}_n\mathrm{C}_k \cdot 1$ であるから、$a_n=1 \ (n=0,1,2,\cdots)$ のとき数列$\{b^{*}_n\}$は $(1+x)^n$ に $x=1$ を代入して得られる。よって $b^{*}_n=(1+1)^n=2^n \ (n=0,1,2,\cdots)$ となるから、こちらも母関数により正しく求められている。

　《解答例》

$a_n$の母関数$f(x)$は $f(x)=\dfrac{x}{(1-x)^2}$ であるから、数列$\{b_n\}$の母関数$F(x)$は$$\small \begin{align}&\ \ \ \ \ F(x) \\ &=\dfrac{1}{1-x}f\left(-\dfrac{x}{1-x}\right) \\ &=\dfrac{1}{1-x} \cdot \dfrac{-\dfrac{x}{1-x}}{\left(1+\dfrac{x}{1-x}\right)^2} \\ &=\dfrac{-x}{(1-x+x)^2} \\ &=-x \end{align}$$となる。故に数列$\{b_n\}$は$$\small \color{red}{b_0=0、b_1=-1、b_n=0 \ (n=2,3,4,\cdots)}$$である。

また、数列$\{b^{*}_n\}$の母関数$F^{*}(x)$は$$\small \begin{align}&\ \ \ \ \ F^{*}(x) \\ &=\dfrac{1}{1-x}f\left(\dfrac{x}{1-x}\right) \\ &=\dfrac{1}{1-x} \cdot \dfrac{\dfrac{x}{1-x}}{\left(1-\dfrac{x}{1-x}\right)^2} \\ &= \dfrac{x}{(1-2x)^2} \end{align}$$となる。故に数列$\{b^{*}_n\}$は第２節の$(1.9)$式を用いて$$\small \color{red}{b^{*}_n={}_n\mathrm{C}_1\cdot 2^{n-1}=n \cdot 2^{n-1} \ (n=0,1,2,\cdots)}$$である。

これらの結果が正しいことを示すための準備として、以下の関係式を理解しよう。$$\small \begin{align} (1+x)^{n}&=1+{}_n\mathrm{C}_1 x+{}_n\mathrm{C}_2 x^2+{}_n\mathrm{C}_3 x^3 + \cdots \\ &\ \ \ \ \ + \cdots + {}_n\mathrm{C}_{n-2} x^{n-2} +{}_n\mathrm{C}_{n-1} x^{n-1}+{}_n\mathrm{C}_n x^n \\ &= \displaystyle \sum^{n}_{k=0} {}_n\mathrm{C}_k x^k \end{align}$$より、$$\small \begin{align}&\ \ \ \ \ \dfrac{d}{dx}(1+x)^{n} \\ &=\color{blue}{n(1+x)^{n-1}} \\ &={}_n\mathrm{C}_1+2 \cdot {}_n\mathrm{C}_2 x+3 \cdot {}_n\mathrm{C}_3 x^2 + \cdots \\ &\ \ \ \ \ + \cdots + (n-2) \cdot {}_n\mathrm{C}_{n-2} x^{n-3} + (n-1) \cdot {}_n\mathrm{C}_{n-1} x^{n-2}+ n \cdot {}_n\mathrm{C}_n x^{n-1} \\ &= \color{blue}{\displaystyle \sum^{n}_{k=1} k \cdot {}_n\mathrm{C}_k x^{k-1}} \end{align}$$となるから、上記の青字部分について両辺に$x$を乗じて、$$nx(1+x)^{n-1}=\displaystyle \sum^{n}_{k=0} k \cdot {}_n\mathrm{C}_k x^{k}$$を得る（この左辺が数列$\{k \cdot {}_n\mathrm{C}_k\}$の母関数である）。

さて、いま $b_n=\displaystyle \sum^{n}_{k=0} (-1)^k {}_n\mathrm{C}_k \cdot k$ であるから、$a_n=n \ (n=0,1,2,\cdots)$ のとき数列$\{b_n\}$は $nx(1+x)^{n-1}$ に $x=-1$ を代入して得られる。よって $b_0=0$、$b_1=-1$、$b_n=0 \ (n=2,3,4,\cdots)$ となり、正しく求められている。

また、$b^{*}_n=\displaystyle \sum^{n}_{k=0} {}_n\mathrm{C}_k \cdot k$ であるから、$a_n=n \ (n=0,1,2,\cdots)$ のとき数列$\{b^{*}_n\}$は $nx(1+x)^{n-1}$ に $x=1$ を代入して得られる。よって $b^{*}_n=n \cdot 1 \cdot (1+1)^{n-1}=n \cdot 2^{n-1} \ (n=0,1,2,\cdots)$ となり、こちらも正しく求められている。

 練習課題

以下、学習のための練習課題として幾つかの問題を提示しておこう。

前へ　戻る