最近解いた漸化式の問題

はじめに

私が最近解いた漸化式の問題の中から，解いていて楽しかったものを2問紹介します．独自の解答付きです．
また，ここに載せている解法と異なるものを見つけたなら，ぜひコメントに書いてください．あなたは満足感と優越感を得られることでしょう．そして中の人は新しい解法に喜びます．Win-Win というやつです．

最後に，解法は折り畳まれていませんので，自分の力だけで解きたいという方はご注意ください．

第1問

解答

$n = 1$のときは明らかであるため，以降では$n \geq 2$のときを考える．
$m \in \mathbb{N}$に対して，新たな関数$f_{n,m}$を次のように定める．
$$ {f_{n,m}(x) = (- 1)^m \int_a^x t^m f_{n - 1}(t) \ dt} $$
$f_{n,0} = f_n$である．
部分積分して整理すると

\begin{align} f_{n,m}(x) &= (- 1)^m \int_a^x \dfrac{1}{m + 1} \left(t^{m + 1} \right)^{\prime} f_{n - 1}(t) \ dt \\ &= (- 1)^m \left( \left\lbrack \dfrac{1}{m + 1} t^{m + 1} f_{n - 1}(t) \right\rbrack_{t = a}^{t = x} - \int_a^x \dfrac{1}{m + 1} t^{m + 1} f_{n - 1}^{\prime}(t) \right) \\ &= \dfrac{(- 1)^m}{m + 1} \left( \left\lbrack t^{m + 1} f_{n - 1}(t) \right\rbrack_{t = a}^{t = x} - \int_a^x t^{m + 1} f_{n - 2}(t) \right) \\ &= \dfrac{(- 1)^{m}}{m + 1} x^{m + 1} f_{n - 1}(x) + \dfrac{1}{m + 1} f_{n - 1,m + 1}(x) \end{align}

となる．ここで$1 \leq k \leq n - 1$なる整数をとると，

\begin{align} f_{n - k + 1,m + k - 1}(x) &= \dfrac{(- 1)^{m + k - 1}}{m + k} x^{m + k} f_{n - k}(x) + \dfrac{1}{m + k} f_{n - k,m + k}(x) \\ \dfrac{m!}{(m + k - 1)!} f_{n - k + 1,m + k - 1}(x) &= \dfrac{m!}{(m + k)!} f_{n - k,m + k}(x) + \dfrac{m!}{(m + k)!} (- 1)^{m + k - 1} x^{m + k} f_{n - k}(x) \\ f_{n,m}(x) &= \dfrac{m!}{(m + n - 1)!} f_{1,m + n - 1}(x) + \sum_{k = 1}^{n - 1} \dfrac{m!}{(m + k)!} (- 1)^{m + k - 1} x^{m + k} f_{n - k}(x) \\ f_n(x) &= \dfrac{(- 1)^{n - 1}}{(n - 1)!} \int_a^x t^{n - 1} f_0(t) \ dt + \sum_{k = 1}^{n - 1} \dfrac{1}{k!} (- 1)^{k - 1} x^k f_{n - k}(x) \\ &= \dfrac{(- 1)^{n - 1}}{(n - 1)!} \int_a^x t^{n - 1} f_0(t) \ dt + \sum_{k = 1}^{n - 1} \dfrac{(- 1)^{n - k - 1}}{(n - k)!} x^{n - k} f_k(x) \\ \dfrac{(- 1)^{n - 1}}{(n - 1)!} \int_a^x t^{n - 1} f_0(t) \ dt &= \sum_{k = 1}^n \dfrac{(- 1)^{n - k}}{(n - k)!} x^{n - k} f_k(x) \ \ \ \cdots (1)\\ \end{align}

となる．これは$n = 1$でも成り立つ．次の操作でこの複雑な式が綺麗に整理されるのでもうしばらく我慢してほしい．

次のような和を考える．
$$ {\sum_{k = 1}^n \dfrac{(- 1)^{k - 1}}{(k - 1)!(n - k)!} x^{n - k} \int_a^x t^{k - 1} f_0(t) \ dt} $$
これは二項定理により

\begin{align} \sum_{k = 1}^n \dfrac{(- 1)^{k - 1}}{(k - 1)!(n - k)!} x^{n - k} \int_a^x t^{k - 1} f_0(t) \ dt &= \dfrac{1}{(n - 1)!} \int_a^x f_0(t) \left( \sum_{k = 1}^n \binom{n - 1}{n - k} x^{n - k} (- t)^{k - 1} \right) \ dt \\ &= \dfrac{1}{(n - 1)!} \int_a^x (x - t)^{n - 1} f_0(t) \ dt \end{align}

となる．一方で，$(1)$式を用いると

\begin{align} \sum_{k = 1}^n \dfrac{(- 1)^{k - 1}}{(k - 1)!(n - k)!} x^{n - k} \int_a^x t^{k - 1} f_0(t) \ dt &= \sum_{k = 1}^n \dfrac{1}{(n - k)!} x^{n - k} \sum_{i = 1}^k \dfrac{(- 1)^{k - i}}{(k - i)!} x^{k - i} f_i(x) \\ &= \sum_{i = 1}^n \dfrac{1}{(n - i)!} x^{n - i} f_i(x) \sum_{k = i}^n \binom{n - i}{k - i} (- 1)^{k - i} \\ &= \sum_{i = 1}^n \dfrac{1}{(n - i)!} x^{n - i} f_i(x) \sum_{k = 0}^{n - i} \binom{n - i}{k} (- 1)^k \\ &= \sum_{i = 1}^n \dfrac{1}{(n - i)!} x^{n - i} f_i(x) \cdot 0^{n - i} \\ &=f_n(x) \end{align}

となる．以上により，
$$ {f_n(x) = \dfrac{1}{(n - 1)!} \int_a^x (x - t)^{n - 1} f_0(t) \ dt} $$
が示せた．

第2問

解答

$a_0 = m$のときの一般項を$a_{m,n}$と書くことにすると，
$$ a_{m,0} = m \ , \ a_{m,n + 1} = \dfrac{1}{n + 2} \left((m + 1)^{n + 2} - 1 - \sum_{k = 0}^n {}_{n + 2} \mathrm{C}_k \cdot a_{m,k} \right) $$
となる．まず，$m = 0$のときを考える(問題文で$m$は自然数と書いており正の整数だと捉えた人もいるだろうが，今回の解法では$m = 0$の場合を考えたほうが楽である)．
$$ a_{0,0} = 0 \ , \ a_{0,n + 1} = - \dfrac{1}{n + 2} \sum_{k = 0}^n {}_{n + 2} \mathrm{C}_k \cdot a_{0,k} $$
となる．一般項はすぐにわかるように$a_{0,n} = 0$である．

さて，ここからがこの漸化式の面白いところである．$a_{m,n}$の$n$に関しての漸化式を式変形し整理していく．
\begin{align} a_{m,n + 1} &= \dfrac{1}{n + 2} \left((m + 1)^{n + 2} - 1 - \sum_{k = 0}^n {}_{n + 2} \mathrm{C}_k \cdot a_{m,k} \right) \\ &= \dfrac{1}{n + 2} \left( \sum_{k = 0}^{n + 2} {}_{n + 2} \mathrm{C}_k \ m^k - 1 - \sum_{k = 0}^n {}_{n + 2} \mathrm{C}_k \cdot a_{m,k} \right) \\ &= \dfrac{1}{n + 2} \left(m^{n + 2} + (n + 2)m^{n + 1} - 1 + \sum_{k = 0}^n {}_{n + 2} \mathrm{C}_k \ m^k - \sum_{k = 0}^n {}_{n + 2} \mathrm{C}_k \cdot a_{m,k} \right) \\ &= \dfrac{1}{n + 2} \left(m^{n + 2} + (n + 2)m^{n + 1} - 1 - \sum_{k = 0}^n {}_{n + 2} \mathrm{C}_k \ (a_{m,k} - m^k) \right) \\ \end{align}
$b_{m,n} = a_{m,n} - m^n$とおくと，$b_{m,0} = m - 1$であり，
\begin{align} b_{m,n + 1} &= \dfrac{1}{n + 2} \left(m^{n + 2} + (n + 2)m^{n + 1} - 1 - \sum_{k = 0}^n {}_{n + 2} \mathrm{C}_k \cdot b_{m,k} \right) - m^{n + 1} \\ &= \dfrac{1}{n + 2} \left(m^{n + 2} - 1 - \sum_{k = 0}^n {}_{n + 2} \mathrm{C}_k \cdot b_{m,k} \right) \\ \end{align}
となり，$b_{m,n} = a_{m - 1,n}$であるとわかる．よって次の等式が成り立つ．
$$ a_{m,n} - a_{m - 1,n} = m^n $$
これで$m$に関する階差数列を求めることができた．よって数列$\lbrace a_n \rbrace$の一般項は
$$ a_n = a_{0,n} + \sum_{k = 1}^m (a_{k,n} - a_{k - 1,n}) = \sum_{k = 1}^m k^n $$
により$\displaystyle{a_n = \sum_{k = 1}^m k^n}$となる．