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

$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{align*} a_{n + 1, n} &= f(n) a_{n, n} + g(n) a_{n, n -1} \\ &= f(n) a_{n, n} + g(n) \left\{ 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}\right\} \\ &= g(1) \cdots g(n) a_{1, 0} + \sum_{k = 1}^n f(k) g(k + 1) \cdots g(n) a_{k,k} \end{align*}
となり成立. $m = 1$ ならば
\begin{align*} a_{n + 1, 1} &= f(1) a_{n, 1} + g(1) a_{n, 0} \\ &= f(1) \left\{ \sum_{k = 1}^{n - 1} f(1)^{n - k- 1} g(1)a_{k, 0} + f(1)^{n - 1}a_{1, 1}\right\} + 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{align*}
となり成立. $1 < m < n$ ならば
\begin{align*} a_{n + 1, m} &= f(m)a_{n, m} +g(m) a_{n, m - 1} \\ &= f(m) \left\{\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} \right.\\ &\quad \left. + \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} \right\} \\ &\quad + g(m) \left\{ \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}\right. \\ &\quad \left. + \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}\right\} \\ &= \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} \\ &\quad + \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{align*}
となり成立する. 以上から示された.

定理1より, 相異なる $x_1, \ldots, 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 \neq k}(x_k - x_l)} $$
を示せば十分. まずは $n \geq 2$ かつ $a = 0, 1, \ldots, n - 2$ のとき
$$ \sum_{k = 1}^{n} \frac{x_k^a}{\prod_{l \neq k}(x_k - x_l)} = 0 $$
となることを示す. $i < j$ のとき左辺に $x_j - x_i$ をかけて $x_j \to x_i$ とすると
$$ \frac{x_i^a}{\prod_{k \neq i, j}(x_i - x_k)} - \frac{x_i^a}{\prod_{k \neq i, j}(x_i - x_k)} = 0 $$
となる. よって
$$ \prod_{i < j} (x_j - x_i) \sum_{k = 1}^{n} \frac{x_k^a}{\prod_{l \neq k}(x_k - x_l)} $$
は次数が高々
$$ \binom{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 \neq k}(x_k - x_l)} $$
を $n$ に関する数学的帰納法により示す. $n = 1$ のときは自明. $n$ までで成立しているときに $n + 1$ のときでも成立していることを示す.
\begin{align*} \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 \neq k, n + 1}(x_k - x_l)} \\ &= \sum_{k = 1}^{n} \frac{x_k^{n + m - 1}}{\prod_{l \neq 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 \neq 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 \neq k}(x_k - x_l)} \end{align*}
ここで, 先に示していたことから
$$ \sum_{k = 1}^{n + 1} \frac{x_k^{n - 1}}{\prod_{l \neq k}(x_k - x_l)} = 0 $$
が成立している. よって
\begin{align*} \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 \neq k}(x_k - x_l)} + x_{n + 1}^{m + 1} \cdot \frac{x_{n + 1}^{n - 1}}{\prod_{l \neq n + 1}(x_{n + 1} - x_l)} \\ &= \sum_{k = 1}^{n + 1} \frac{x_k^{n + m}}{\prod_{l \neq k}(x_k - x_l)} \end{align*}
となり示された.

\begin{align*} &\sum_{k = 1}^{i} \frac{f(k) \cdot f(i)^{n - k - 1}}{\prod_{k \leq j \leq m, \, j \neq i} \{ f(i) - f(j)\}} \\ &= \frac{f(i)^{n - i}}{\prod_{i < j \leq m} \{ f(i) - f(j)\}} + \sum_{k = 1}^{i - 1} \frac{f(k) \cdot f(i)^{n - k - 1}}{\prod_{k \leq j \leq m, \, j \neq i} \{ f(i) - f(j)\}} \\ &= \frac{f(i)^{n - i}}{\prod_{i < j \leq 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 \leq j \leq m, \, j \neq i} \{ f(i) - f(j)\}} \\ &= \frac{f(i)^{n -i}}{\prod_{i < j \leq m} \{ f(i) - f(j)\}} + \sum_{k = 1}^{i - 1} \left\{\frac{f(i)^{n - k}}{\prod_{k \leq j \leq m, \, j \neq i} \{ f(i) - f(j)\}} - \frac{f(i)^{n - k - 1}}{\prod_{k + 1 \leq j \leq m, \, j \neq i} \{ f(i) - f(j)\}}\right\} \\ &= \frac{f(i)^{n - 1}}{\prod_{1 \leq j \leq m, \, j \neq i}\{ f(i) - f(j)\}} \end{align*}

定理3に $a_{k, k}$ の条件を代入すると
\begin{align*} a_{n, m} = g(1) \cdots g(m) \left\{ \sum_{i = 1}^{m} \frac{\sum_{k = 1}^{n - m} a_{k, 0} f(i)^{n - k - 1}}{\prod_{1 \leq j \leq m, \, j \neq 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 \leq j \leq m, \, j \neq i}\{f(i) - f(j)\}} \right\} \end{align*}
を得る. $\{ \quad \}$ 内の二項目について $1 \leq k \leq m, \, k \leq i \leq m$ と $1 \leq i \leq m, \, 1 \leq k \leq i$ は同値であるので, 補題4より
\begin{align*} \sum_{k = 1}^{m} \sum_{i = k}^{m} \frac{f(k) \cdot f(i)^{n - k - 1}}{\prod_{k \leq j \leq m, \, j \neq i}\{f(i) - f(j)\}} &= \sum_{i = 1}^{m} \sum_{k = 1}^{i} \frac{f(k) \cdot f(i)^{n - k - 1}}{\prod_{k \leq j \leq m, \, j \neq i}\{f(i) - f(j)\}} \\ &= \sum_{i = 1}^{m} \frac{f(i)^{n - 1}}{\prod_{1 \leq j \leq m, \, j \neq i}\{ f(i) - f(j)\}} \end{align*}
が従う. 以上から上記の二つの式を合わせると直ちに従う.