4.母関数の応用~二項変換とその逆変換


4.母関数の応用~二項変換と逆変換

前へ 戻る


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

 
《(交代)二項変換((alternating) binomial transform)》数列$\{a_n\}$に対して以下の操作により新たな数列$\{b_n\}$を構成する方法を「(交代)二項変換」という。$$b_n=\displaystyle \sum^{n}_{k=0} (-1)^k {}_n\mathrm{C}_k a_k \tag{2.1.0}$$このとき、数列$\{a_n\}$の通常型母関数を$f(x)$とすれば、数列$\{b_n\}$の通常型母関数$F(x)$は$$F(x)=\dfrac{1}{1-x}f\left(-\dfrac{x}{1-x}\right) \tag{2.1.1}$$で与えられる。また、数列$\{a_n\}$の指数型母関数を$g(x)$とすれば、数列$\{b_n\}$の指数型母関数$G(x)$は$$G(x)=e^x g(-x)\tag{2.1.2}$$で与えられる。

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

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

 
《(単純)二項変換((simple) binomial transform)》数列$\{a_n\}$に対して以下の操作により新たな数列$\{b^{*}_n\}$を構成する方法を「(単純)二項変換」という。$$b^{*}_n=\displaystyle \sum^{n}_{k=0} {}_n\mathrm{C}_k a_k \tag{2.2.0}$$このとき、数列$\{a_n\}$の通常型母関数を$f(x)$とすれば、数列$\{b^{*}_n\}$の通常型母関数$F^{*}(x)$は$$F^{*}(x)=\dfrac{1}{1-x}f\left(\dfrac{x}{1-x}\right) \tag{2.2.1}$$で与えられる。また、数列$\{a_n\}$の指数型母関数を$g(x)$とすれば、数列$\{b^{*}_n\}$の指数型母関数$G^{*}(x)$は$$G^{*}(x)=e^x g(x) \tag{2.2.2}$$で与えられる。

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


《二項変換の合成と母関数》

(難解に感じたら例題編まで読み飛ばしてよい)

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

$$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)$ であるから、

$$\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)であることを意味している。式化すると以下のようになる。

$$\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)$$となる。これに更に交代二項変換を施してみると、

$$\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} $$

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

$$\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)$に交代二項変換を施してから単純二項変換を施すと、次のようになる。

$$\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)$に単純二項変換を2回施すと、次のようになる。$$\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}$$

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

$\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}$

$\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}$


 

●   ●   ●   ●   ●

 

《例題編》

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


 《例題1》

$a_n=1 \ (n=0,1,2,\cdots)$ で定まる数列$\{a_n\}$に対して、交代二項変換を施してできる数列を$\{b_n\}$、単純二項変換を施してできる数列を$\{b^{*}_n\}$とする。数列$\{b_n\}$及び$\{b^{*}_n\}$求めよ。

 《解答例》

$a_n$の母関数$f(x)$は $f(x)=\dfrac{1}{1-x}$ であるから、数列$\{b_n\}$の母関数$F(x)$は$$\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\}$は$$\color{red}{b_0=1、b_n=0 \ (n=1,2,3,\cdots)}$$である。

また、数列$\{b^{*}_n\}$の母関数$F^{*}(x)$は$$\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\}$は$$\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)$ となるから、こちらも母関数により正しく求められている。

 


 《例題2》

$a_n=n \ (n=0,1,2,\cdots)$ で定まる数列$\{a_n\}$に対して、交代二項変換を施してできる数列を$\{b_n\}$、単純二項変換を施してできる数列を$\{b^{*}_n\}$とする。数列$\{b_n\}$及び$\{b^{*}_n\}$求めよ。

 《解答例》

$a_n$の母関数$f(x)$は $f(x)=\dfrac{x}{(1-x)^2}$ であるから、数列$\{b_n\}$の母関数$F(x)$は$$\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\}$は$$\color{red}{b_0=0、b_1=-1、b_n=0 \ (n=2,3,4,\cdots)}$$である。

また、数列$\{b^{*}_n\}$の母関数$F^{*}(x)$は$$\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\}$は第2節の$(1.9)$式を用いて$$\color{red}{b^{*}_n={}_n\mathrm{C}_1\cdot 2^{n-1}=n \cdot 2^{n-1} \ (n=0,1,2,\cdots)}$$である。

※$(1.9)$式とは次の公式である。

(再掲)$\color{red}{\dfrac{1}{(1-x)^{m+1}}=\displaystyle \sum_{n=0}^{\infty} {}_{n+m}\mathrm{C}_m x^n}$


これらの結果が正しいことを示すための準備として、以下の関係式を理解しよう。

$$\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}$$

より、

$$\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)$ となり、こちらも正しく求められている。

 

●   ●   ●   ●   ●

 

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


《練習課題1》

$$S_n={}_n\mathrm{C}_0 +3 \cdot {}_n\mathrm{C}_1+5 \cdot {}_n\mathrm{C}_k+ \cdots + (2n+1)  \cdot {}_n\mathrm{C}_n$$が $(n+1) \cdot 2^n$ に等しいことを母関数から確かめよ。

» 解き方はこちら

 《解答例》

$S_n$は数列 $a_n=2n+1$ に単純二項変換を施すと得られる。数列 $a_n=2n+1$ の母関数$f(x)$は$$\begin{align} f(x)&= 2 \cdot \dfrac{x}{(1-x)^2}+\dfrac{1}{1-x} \\ &=\dfrac{x+1}{(1-x)^2} \end{align}$$であるから$S_n$の母関数$F^{*}(x)$は$$\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}+1}{\left(1-\dfrac{x}{1-x}\right)^2} \\ &= \dfrac{1}{(1-2x)^2} \end{align}$$となる。故に数列$\{S_n\}$は$$S_n={}_{n+1}\mathrm{C}_1 \cdot 2^{n}=\color{red}{(n+1) \cdot 2^{n} \ (n=0,1,2,\cdots)}$$である。(※$n$次の係数の計算には$(1.9)$式を用いた)

» 閉じる

 


《練習課題2》

$n$番目のモンモール数$a_n$の単純二項変換が階乗数$n!$になることを母関数から確かめよ。なお、モンモール数の指数型母関数$g(x)$は$$g(x)=\dfrac{e^{-x}}{1-x}$$で与えられる。

» 解き方はこちら

 《解答例》

$$e^x g(x)=e^x \cdot \dfrac{e^{-x}}{1-x}=\dfrac{1}{1-x}$$である。階乗数$n!$の指数型母関数$h(x)$は $h(x)=\dfrac{1}{1-x}$ であるから、$e^x g(x)=h(x)$ となり確かに$n$番目のモンモール数$a_n$の単純二項変換が階乗数$n!$になっている。

(参考:第2回「#旧帝戦数学部門」を解いてみた

» 閉じる

 


《練習課題3》

$$A_n=\displaystyle \sum^{n}_{k=0} {{}_n\mathrm{C}_k}^2$$を$n$の式で表せ。

» 解き方はこちら

 《解答例》

二項係数${}_n\mathrm{C}_k$の母関数$f(x)$は$$f(x)=(1+x)^n$$である。これに対して単純二項変換を施すと、

$$\begin{align}&\ \ \ \ \ \dfrac{1}{1-x}\left(1-\dfrac{x}{1-x}\right)^n \\ &=\dfrac{1}{(1-x)^{n+1}} \\ &=\displaystyle \sum^{\infty}_{k=0} {}_{n+k}\mathrm{C}_k x^k \ \ \ (\because (1.9))\end{align}$$

となる。よって$x^n$の係数は ${}_{2n}\mathrm{C}_n$ となるから、$$A_n=\displaystyle \sum^{n}_{k=0} {{}_n\mathrm{C}_k}^2=\color{red}{{}_{2n}\mathrm{C}_n}$$である。

» 閉じる

 


《練習課題4》

$$S_n=0^2 \cdot {}_n\mathrm{C}_0 +1^2 \cdot {}_n\mathrm{C}_1+2^2 \cdot {}_n\mathrm{C}_2+ \cdots + n^2 \cdot {}_n\mathrm{C}_n$$が $n(n+1) \cdot 2^{n-2}$ に等しいことを母関数から確かめよ。

» 解き方はこちら

 《解答例》

平方数$k^2$の母関数$f(x)$は$$f(x)=\dfrac{x(1+x)}{(1-x)^3}$$である。これに対して単純二項変換を施すと、

$$\begin{align}&\ \ \ \ \ \dfrac{1}{1-x}\dfrac{\dfrac{1}{1-x}\left(1+\dfrac{x}{1-x}\right)}{\left(1-\dfrac{x}{1-x}\right)^3} \\ &=\dfrac{x}{(1-2x)^{3}} \\ &=x\displaystyle \sum^{\infty}_{k=0} {}_{n+2}\mathrm{C}_2 \cdot 2^n x^{n} \ \ \ (\because (1.9)) \\ &=\displaystyle \sum^{\infty}_{k=0} {}_{n+2}\mathrm{C}_2 \cdot 2^n x^{n+1}\end{align}$$

となる。故に$x^n$の係数は$$\begin{align} {}_{n+1}\mathrm{C}_2 \cdot 2^{n-1}&=\dfrac{n(n+1)}{2} \cdot 2^{n-1} \\ &=n(n+1) \cdot 2^{n-2} \end{align}$$となるから、$$S_n=\color{red}{n(n+1) \cdot 2^{n-2}}$$である。

» 閉じる

 


《発展例題》

$$B_n=\displaystyle \sum^{n}_{k=0} (-1)^k {{}_n\mathrm{C}_k}^2 \ (n=0,1,2,\cdots)$$を$n$の式で表せ。

» 答えはこちら

$$B_n=\begin{cases} (-1)^m {}_{2m}\mathrm{C}_{m} & (\text{for} \ n=2m) \\ 0 & (\text{for} \ n=2m+1)\end{cases}$$

但し$m$は$0$以上の整数とする。

» 閉じる

 


前へ 戻る