二重数列の漸化式（二変数漸化式）の解法

$n$ に関する数学的帰納法により示す.
$n=2$ のとき, $0<m<n=2$ より $m=1$.
$$a_{2,1}=f(1)a_{1,1}+g(1)a_{1,0}$$
これは成立している.

$n$ のときに成立していると仮定して $n+1$ のとき成立することを示す. $m=n$ ならば
$$\begin{array}{rl}{a}_{n+1,n}& =f(n)a_{n,n}+g(n)a_{n,n-1}\\ & =f(n)a_{n,n}+g(n)\{g(1)\cdots g(n-1)a_{1,0}+\sum _{k=1}^{n-1}f(k)g(k+1)\cdots g(n-1)a_{k,k}\}\\ & =g(1)\cdots g(n)a_{1,0}+\sum _{k=1}^{n}f(k)g(k+1)\cdots g(n)a_{k,k}\end{array}$$
となり成立. $m=1$ ならば
$$\begin{array}{rl}{a}_{n+1,1}& =f(1)a_{n,1}+g(1)a_{n,0}\\ & =f(1)\{\sum _{k=1}^{n-1}f(1{)}^{n-k-1}g(1)a_{k,0}+f(1{)}^{n-1}{a}_{1,1}\}+g(1)a_{n,0}\\ & =\sum _{k=1}^{n}f(1{)}^{n-k}g(1)a_{k,0}+f(1{)}^n{a}_{1,1}\end{array}$$
となり成立. $1<m<n$ ならば
$$\begin{array}{rl}{a}_{n+1,m}& =f(m)a_{n,m}+g(m)a_{n,m-1}\\ & =f(m)\{\sum _{k=1}^{n-m}\sum _{a_1^{(k)}+\cdots +a_m^{(k)}=n-m-k}f(1{)}^{a_0^{(k)}}\cdots f(m{)}^{a_m^{(k)}}g(1)\cdots g(m)a_{k,0}\\ & +\sum _{k=1}^m\sum _{b_k^{(k)}+\cdots +b_m^{(k)}=n-m-1}f(k{)}^{1+b_k^{(k)}}\cdots f(m{)}^{b_m^{(k)}}g(k+1)\cdots g(m)a_{k,k}\}\\ & +g(m)\{\sum _{k=1}^{n-m+1}\sum _{a_1^{(k)}+\cdots +a_{m-1}^{(k)}=n-m-k+1}f(1{)}^{a_1^{(k)}}\cdots f(m-1{)}^{a_{m-1}^{(k)}}g(1)\cdots g(m-1)a_{k,0}\\ & +\sum _{k=1}^{m-1}\sum _{b_k^{(k)}+\cdots +b_{m-1}^{(k)}=n-m}f(k{)}^{1+b_k^{(k)}}\cdots f(m-1{)}^{b_{m-1}^{(k)}}g(k+1)\cdots g(m-1)a_{k,k}\}\\ & =\sum _{k=1}^{n-m+1}\sum _{a_1^{(k)}+\cdots +a_m^{(k)}=n-m-k+1}f(1{)}^{a_1^{(k)}}\cdots f(m{)}^{a_m^{(k)}}g(1)\cdots g(m)a_{k,0}\\ & +\sum _{k=1}^m\sum _{b_k^{(k)}+\cdots +b_m^{(k)}=n-m}f(k{)}^{1+b_k^{(k)}}\cdots f(m{)}^{b_m^{(k)}}g(k+1)\cdots g(m)a_{k,k}\end{array}$$
となり成立する. 以上から示された.

定理1より, 相異なる $x_1,\dots ,x_n\in \mathbb{C}$ と任意の非負整数 $m$ に対して
$$\sum _{a_1+\cdots +a_n=m}{x}_1^{a_1}\cdots x_n^{a_n}=\sum _{k=1}^n\frac{x_k^{n+m-1}}{\prod _{l\ne k}(x_k-x_l)}$$
を示せば十分. まずは $n\ge 2$ かつ $a=0,1,\dots ,n-2$ のとき
$$\sum _{k=1}^n\frac{x_k^a}{\prod _{l\ne k}(x_k-x_l)}=0$$
となることを示す. $i<j$ のとき左辺に $x_j-x_i$ をかけて $x_j\to x_i$ とすると
$$\frac{x_i^a}{\prod _{k\ne i,j}(x_i-x_k)}-\frac{x_i^a}{\prod _{k\ne i,j}(x_i-x_k)}=0$$
となる. よって
$$\prod _{i<j}(x_j-x_i)\sum _{k=1}^n\frac{x_k^a}{\prod _{l\ne k}(x_k-x_l)}$$
は次数が高々
$$(\genfrac{}{}{0ex}{}{n}{2})\cdot \frac{a}{n-1}=\frac{an}{2}$$
の多項式であるが, これが$0$でないなら因数定理より任意の $i<j$ に対して $x_j-x_i$ を因数にもつ. すなわち次数が ${\displaystyle \frac{n(n-1)}{2}}$ 以上となるがこれは矛盾.よって示された.

次に
$$\sum _{a_1+\cdots +a_n=m}{x}_1^{a_1}\cdots x_n^{a_n}=\sum _{k=1}^n\frac{x_k^{n+m-1}}{\prod _{l\ne k}(x_k-x_l)}$$
を $n$ に関する数学的帰納法により示す. $n=1$ のときは自明. $n$ までで成立しているときに $n+1$ のときでも成立していることを示す.
$$\begin{array}{rl}\sum _{a_1+\cdots +a_{n+1}=m}{x}_1^{a_1}\cdots x_{n+1}^{a_{n+1}}& =\sum _{a_{n+1}=0}^m{x}_{n+1}^{a_{n+1}}\sum _{a_1+\cdots +a_n=m-a_{n+1}}{x}_1^{a_1}\cdots x_n^{a_n}\\ & =\sum _{a_{n+1}=0}^m{x}_{n+1}^{a_{n+1}}\sum _{k=1}^n\frac{x_k^{n+m-a_{n+1}-1}}{\prod _{l\ne k,n+1}(x_k-x_l)}\\ & =\sum _{k=1}^n\frac{x_k^{n+m-1}}{\prod _{l\ne k,n+1}(x_k-x_l)}\cdot \frac{{\left(\frac{x_{n+1}}{x_k}\right)}^{m+1}-1}{\frac{x_{n+1}}{x_k}-1}\\ & =\sum _{k=1}^n\frac{x_k^{n-1}}{\prod _{l\ne k,n+1}(x_k-x_l)}\cdot \frac{x_{n+1}^{m+1}-x_k^{m+1}}{x_{n+1}-x_k}\\ & =\sum _{k=1}^n\frac{x_k^{n+m}-x_k^{n-1}{x}_{n+1}^{m+1}}{\prod _{l\ne k}(x_k-x_l)}\end{array}$$
ここで, 先に示していたことから
$$\sum _{k=1}^{n+1}\frac{x_k^{n-1}}{\prod _{l\ne k}(x_k-x_l)}=0$$
が成立している. よって
$$\begin{array}{rl}\sum _{a_1+\cdots +a_{n+1}=m}{x}_1^{a_1}\cdots x_{n+1}^{a_{n+1}}& =\sum _{k=1}^n\frac{x_k^{n+m}}{\prod _{l\ne k}(x_k-x_l)}+x_{n+1}^{m+1}\cdot \frac{x_{n+1}^{n-1}}{\prod _{l\ne n+1}(x_{n+1}-x_l)}\\ & =\sum _{k=1}^{n+1}\frac{x_k^{n+m}}{\prod _{l\ne k}(x_k-x_l)}\end{array}$$
となり示された.

$$\begin{array}{rl}& \sum _{k=1}^i\frac{f(k)\cdot f(i{)}^{n-k-1}}{\prod _{k\le j\le m,j\ne i}\{f(i)-f(j)\}}\\ & =\frac{f(i{)}^{n-i}}{\prod _{i<j\le m}\{f(i)-f(j)\}}+\sum _{k=1}^{i-1}\frac{f(k)\cdot f(i{)}^{n-k-1}}{\prod _{k\le j\le m,j\ne i}\{f(i)-f(j)\}}\\ & =\frac{f(i{)}^{n-i}}{\prod _{i<j\le m}\{f(i)-f(j)\}}+\sum _{k=1}^{i-1}\frac{\{f(i)-(f(i)-f(k))\}\cdot f(i{)}^{n-k-1}}{\prod _{k\le j\le m,j\ne i}\{f(i)-f(j)\}}\\ & =\frac{f(i{)}^{n-i}}{\prod _{i<j\le m}\{f(i)-f(j)\}}+\sum _{k=1}^{i-1}\{\frac{f(i{)}^{n-k}}{\prod _{k\le j\le m,j\ne i}\{f(i)-f(j)\}}-\frac{f(i{)}^{n-k-1}}{\prod _{k+1\le j\le m,j\ne i}\{f(i)-f(j)\}}\}\\ & =\frac{f(i{)}^{n-1}}{\prod _{1\le j\le m,j\ne i}\{f(i)-f(j)\}}\end{array}$$

定理3に $a_{k,k}$ の条件を代入すると
$$\begin{array}{r}{a}_{n,m}=g(1)\cdots g(m)\{\sum _{i=1}^m\frac{\sum _{k=1}^{n-m}{a}_{k,0}f(i{)}^{n-k-1}}{\prod _{1\le j\le m,j\ne i}\{f(i)-f(j)\}}+a_{0,0}\sum _{k=1}^m\sum _{i=k}^m\frac{f(k)\cdot f(i{)}^{n-k-1}}{\prod _{k\le j\le m,j\ne i}\{f(i)-f(j)\}}\}\end{array}$$
を得る. $\{\}$ 内の二項目について $1\le k\le m,k\le i\le m$ と $1\le i\le m,1\le k\le i$ は同値であるので, 補題4より
$$\begin{array}{rl}\sum _{k=1}^m\sum _{i=k}^m\frac{f(k)\cdot f(i{)}^{n-k-1}}{\prod _{k\le j\le m,j\ne i}\{f(i)-f(j)\}}& =\sum _{i=1}^m\sum _{k=1}^i\frac{f(k)\cdot f(i{)}^{n-k-1}}{\prod _{k\le j\le m,j\ne i}\{f(i)-f(j)\}}\\ & =\sum _{i=1}^m\frac{f(i{)}^{n-1}}{\prod _{1\le j\le m,j\ne i}\{f(i)-f(j)\}}\end{array}$$
が従う. 以上から上記の二つの式を合わせると直ちに従う.