東京大学 2020年度 前期日程 第2次学力試験文系数学 第4問

(1) $$a_{n,2}=\sum _{0\leqq i<j\leqq n-1}{2}^{i+j}\mathrm{.}$$全体の和の平方から同じ項どうしの積を除くと$$a_{n,2}=\frac{1}{2}\{(1+2+\cdots +2^{n-1}{)}^2-(1+2^2+\cdots +2^{2n-2})\}\mathrm{.}$$等比数列の和を代入して$$\begin{array}{rl}{\displaystyle a_{n,2}}& {\displaystyle =\frac{1}{2}\{(2^n-1{)}^2-\frac{4^n-1}{3}\}}\\ {\displaystyle }& {\displaystyle =\frac{4^n-3\cdot 2^n+2}{3}\mathrm{.}}\end{array}$$(2)

各因子から定数項または $2^{m}x$ を選んで展開すると、$x^k$ の係数がちょうど $a_{n,k}$ になる。よって$$f_n(x)=(1+x)(1+2x)\cdots (1+2^{n-1}x)\mathrm{.}$$したがって$$f_{n+1}(x)=(1+2^{n}x)f_n(x)$$および$$f_{n+1}(x)=(1+x)f_n(2x)$$であるから、$$\frac{f_{n+1}(x)}{f_n(x)}=1+2^{n}x,\frac{f_{n+1}(x)}{f_n(2x)}=1+x\mathrm{.}$$(3)

第1の恒等式で $x^{k+1}$ の係数を比較すると$$a_{n+1,k+1}=a_{n,k+1}+2^n{a}_{n,k}\mathrm{.}$$第2の恒等式からは$$a_{n+1,k+1}=2^{k+1}{a}_{n,k+1}+2^k{a}_{n,k}\mathrm{.}$$両式を引いて$$(2^n-2^k)a_{n,k}=(2^{k+1}-1)a_{n,k+1},$$したがって$$\frac{a_{n,k+1}}{a_{n,k}}=\frac{2^n-2^k}{2^{k+1}-1}\mathrm{.}$$これを最初の式へ戻せば$$\begin{array}{rl}{\displaystyle \frac{a_{n+1,k+1}}{a_{n,k}}}& {\displaystyle =2^n+\frac{2^n-2^k}{2^{k+1}-1}}\\ {\displaystyle }& {\displaystyle =\frac{2^k(2^{n+1}-1)}{2^{k+1}-1}\mathrm{.}}\end{array}$$$k=n$ の場合も右辺は $2^n$ となり、式はそのまま成り立つ。

(1) は大きい方の指数を固定した二重和で計算する。(2)の積表示から「$2^{n-1}$ を選ぶか否か」で漸化式を作り、$a_{n,k}$ の明示公式を数学的帰納法で確かめる。(3)は明示公式の比をとり、連続する因子を消去する。

(1)

大きい方の指数を $j$ とすると$$\begin{array}{rl}{\displaystyle a_{n,2}}& {\displaystyle =\sum _{j=1}^{n-1}{2}^j(1+2+\cdots +2^{j-1})}\\ {\displaystyle }& {\displaystyle =\sum _{j=1}^{n-1}(4^j-2^j)}\\ {\displaystyle }& {\displaystyle =\frac{4^n-4}{3}-(2^n-2)}\\ {\displaystyle }& {\displaystyle =\frac{4^n-3\cdot 2^n+2}{3}\mathrm{.}}\end{array}$$(2)

選んだ指数を係数として記録するため$$f_n(x)=(1+x)(1+2x)\cdots (1+2^{n-1}x)\mathrm{.}$$よって直ちに$$\frac{f_{n+1}(x)}{f_n(x)}=1+2^{n}x,\frac{f_{n+1}(x)}{f_n(2x)}=1+x\mathrm{.}$$(3)

$k$ 個を選ぶとき $2^{n-1}$ を選ばない場合と選ぶ場合に分けると$$a_{n,k}=a_{n-1,k}+2^{n-1}{a}_{n-1,k-1}\mathrm{.}$$この漸化式から数学的帰納法により$$a_{n,k}=2^{k(k-1)\mathrm{/}2}\frac{(2^n-1)(2^{n-1}-1)\cdots (2^{n-k+1}-1)}{(2^k-1)(2^{k-1}-1)\cdots (2-1)}$$を得る。

実際、右辺を $B_{n,k}$ とおくと$$\frac{B_{n-1,k}}{B_{n,k}}=\frac{2^{n-k}-1}{2^n-1},$$また$$\frac{2^{n-1}{B}_{n-1,k-1}}{B_{n,k}}=\frac{2^{n-k}(2^k-1)}{2^n-1}\mathrm{.}$$この2つの比の和は1なので、$B_{n,k}$ は上の漸化式を満たす。初期値も一致するから明示公式が従う。

したがって、連続する因子を消去すれば$$\frac{a_{n+1,k+1}}{a_{n,k}}=2^k\frac{2^{n+1}-1}{2^{k+1}-1}\mathrm{.}$$