奈良素敵大学模試(自作模試)大問2〜解説〜
問題
以下の漸化式で与えられる数列$\{a_n\},\{b_n\}$を考える。ただし、$n$は非負整数であるとし、$\{a_n\}$の初項は$a_0=1$とする。
$
\left\{
\begin{array}{l}
\displaystyle a_{n+1}=\sum_{k=0}^na_ka_{n-k} \\
\displaystyle b_{n+1}=\sum_{k=0}^n (k+1)a_ka_{n-k}
\end{array}
\right.$
(1)$b_n$を$a_n$で表わせ。
(2)$\displaystyle a_{n+1}=\frac{2(2n+1)}{n+2}a_n$を証明せよ。
(3)それぞれの数列の一般項$a_n,b_n$を求めよ。
(4)$\displaystyle \lim_{n \to \infty} \sqrt[n]{a_n}$を求めよ。
まだ解いていない方はこちらから 記事 へ飛べます。答えを見たくない場合はどうぞ。
作問の意図
この数列$a_n$は「カタラン数」(Catalan number)の漸化式を満たしています。
今初めて聞いたという方は
高校数学の美しい物語さんの記事
を参照してください(分かりやすいです)。
場合の数を求めるときによく出てくるパターンの数列です。数学オリンピックや、まれに大学入試の題材になることもあります。
この漸化式を解く際、一般的には以下のような「母関数」を使った解法が有名です。(概略を示します)
$n$番目のカタラン数を$C_n$とおくと、母関数は
$$\displaystyle\sum_{n=0}^{\infty}C_nx^n=1+x+2x^2+5x^3+...$$である。これを$f(x)$とおくと$f(x)^2=\displaystyle\frac{f(x)-1}{x}$が成り立つからこれを解くと、
$$f(x)=\displaystyle \frac{1-\sqrt{1-4x}}{2x}$$である。(符号は初期条件から決定する)
$\sqrt{1-4x}$を二項展開して係数比較することにより、一般項が分かる。
そこで、これ以外にもこの漸化式を直接解く別解がないだろうかと考えて出来たのがこの問題です。
$b_n$を持ち出すことにより数学的帰納法での二項間漸化式の証明を可能にしています。
また、(4)の問題はウォリスの公式から得られる、
$$C_n \sim \displaystyle\frac{4^n}{n^{\frac{3}{2}}\sqrt{\pi}}$$を背景にしています。
では解説に移りましょう。
解説
(1)$b_n$を逆順に並べて、
$$b_n=a_0a_{n-1}+2a_1a_{n-2}+\cdots+na_{n-1}a_0$$$$b_n=na_{n-1}a_0+(n-1)a_{n-2}a_1+\cdots+a_0a_{n-1}$$ 辺辺加えることにより、
$$2b_n=(n+1)a_n\Leftrightarrow b_n=\frac{n+1}{2}a_n$$(2)
まず$n=0$のとき$a_1=a_0=1$より成り立つ。
次に$n=1,2,3,\cdots,m$($m$は自然数)のとき、$0\leq k\leq m$となる非負整数$k$について、$\displaystyle a_{k+1}=\frac{2(2k+1)}{k+2}a_k$が成り立つと仮定する。
$n=m+1$のとき、$b_{m+2}$を考えて、
$b_{m+2}=\displaystyle\sum_{k=0}^{m+1}(k+1)a_ka_{m-k+1}=a_0a_{m+1}+\sum_{k=1}^{m+1}(k+1)a_ka_{m-k+1}=a_{m+1}+\sum_{k=0}^{m}(k+2)a_{k+1}a_{m-k}$
仮定より、
$\ \ \ \ \ \ \ \ =\displaystyle a_{m+1}+\sum_{k=0}^{m}2(2k+1)a_ka_{m-k}=a_{m+1}+4\sum_{k=0}^{m}(k+1)a_ka_{m-k}-2\sum_{k=0}^{m}a_ka_{m-k}$
$\ \ \ \ \ \ \ \ =4b_{m+1}-a_{m+1}$
(1)の結果より、
$\displaystyle a_{m+1}=2(m+2)a_{m+1}-\frac{m+3}{2}a_{m+2}\Leftrightarrow a_{(m+1)+1}=\frac{2(2(m+1)+1)}{(m+1)+2}a_{m+1}$
ゆえに$n=m+1$でも成り立つ。
よってすべての非負整数$n$について与式は成り立つ。
(3)
(2)より、$a_n=\displaystyle\frac{2(2n-1)}{n+1}\cdot \frac{2(2n-3)}{n}\cdots \frac{2\cdot 1}{2}a_0=\frac{2^n\cdot(2n-1)!!}{(n+1)!}$
($!!$は二重階乗。つまり$(2n-1)!!$は$2n-1$以下で$2n-1$と同じ偶奇性をもつ数の総積)
ここで$\displaystyle2^n\cdot(2n-1)!!=\frac{(2n)!}{n!}$であるから、(列挙して素因数分解すれば分かる)
$$a_n=\displaystyle\frac{(2n)!}{n!(n+1)!}=\frac{{}_{2n}{\mathrm{C}}_{n}}{n+1},b_n=\frac{n+1}{2}\cdot\frac{{}_{2n}{\mathrm{C}}_{n}}{n+1}={}_{2n-1}{\mathrm{C}}_{n}$$となる。
(4)
求める値を$I$とおくと、
$I=\displaystyle\lim_{n \to \infty}\sqrt[n]{a_n}=\lim_{n \to \infty}\frac{\sqrt[n]{{}_{2n}{\mathrm{C}_{n}}}}{\sqrt[n]{n+1}}$
ここで分子を$J$、分母を$K$とおく。
$\displaystyle\lim_{n \to \infty}K=\lim_{n \to \infty}e^{\frac{\log(n+1)}{n}}=e^0=1$
($\displaystyle\lim_{n\to \infty}\frac{\log(n+1)}{n}=0$を用いた)
よって、$I=\displaystyle\frac{\displaystyle\lim_{n \to \infty}J}{\displaystyle\lim_{n \to \infty}K}=\displaystyle\lim_{n\to\infty}J$として良い。(商の極限)
次に$\log J=\displaystyle\frac{\log((2n)!)-2\log n!}{n}$であるから、$\log n!$を評価すれば良い。
$\log n!=\log1+\log2+\cdots+\log n$であるから$y=\log x$のグラフによる面積評価より、
$\displaystyle\int_{1}^{n}\log xdx< \log n!< \int_{1}^{n}\log xdx+\log n \Leftrightarrow n\log n-n+1<\log n!< (n+1)\log n-n+1$
同様にして、
$\displaystyle 2n\log2n-2n+1<\log(2n!)<(2n+1)\log2n-2n+1$
したがって、
$\displaystyle\log4-\frac{1}{n}<\frac{\log(2n!)-2\log n!}{n}<\log4+\frac{\log2-\log n}{n}-\frac{1}{n}$
ゆえに、はさみうちの原理より
$\displaystyle\lim_{n\to\infty}\log J=\log4$
対数関数の連続性より、
$\displaystyle\lim_{n\to\infty}J=4$
よって$I=4$である。
※別解
ベルトラン・チェビシェフの定理(Bertrand–Chebyshev theorem)のエルデシュ(Paul Erdős)による証明を知っているなら
$\displaystyle\frac{4^n}{n}\leq{}_{2n}{\mathrm{C}_n}\leq4^n$や$\displaystyle\frac{4^n}{2\sqrt{n}}\leq{}_{2n}{\mathrm{C}_n}\leq\frac{4^n}{2}$(一定以上の$n$で成り立つ)
などの評価がすぐに思い浮かぶでしょう。
もちろんこれらの不等式を示す($c_n={}_{2n}{\mathrm{C}_n}$の漸化式を用いた数学的帰納法による)ことで$J$の極限をはさみうちの原理から求めることが出来ます。誘導にしても良いかも。
これ以外に別解などあればぜひコメントください。指摘も歓迎です。