トップ› 東京大学› 2020年› 文系第4問

東京大学 2020年文系第4問解説

方針・初手

$n$ 個の整数の集合 $\{2^0, 2^1, \dots, 2^{n-1}\}$ から $k$ 個選んだ積の和 $a_{n,k}$ は、整式 $\prod_{m=0}^{n-1} (1 + 2^m x)$ を展開したときの $x^k$ の係数に一致する。この性質を用いると、見通しよく解き進めることができる。

(1) は基本的な対称式の関係式 $( \sum x_i )^2 = \sum x_i^2 + 2 \sum x_i x_j$ を用いる方法が確実である。 (2) は $f_n(x)$ を因数分解された形で表すことで、容易に比を計算できる。 (3) は (2) で得られた2つの整式の関係式を利用し、両辺の $x^{k+1}$ の係数を比較することで $a_{n+1,k+1}$、$a_{n,k+1}$、$a_{n,k}$ の間の漸化式を導出し、そこから目的の式を作る。

解法1

(1)

$n$ 個の整数 $2^0, 2^1, \dots, 2^{n-1}$ の和を $S_1$、それぞれの2乗の和を $S_2$ とおく。

$$ S_1 = \sum_{m=0}^{n-1} 2^m = \frac{1 \cdot (2^n - 1)}{2 - 1} = 2^n - 1 $$

$$ S_2 = \sum_{m=0}^{n-1} (2^m)^2 = \sum_{m=0}^{n-1} 4^m = \frac{1 \cdot (4^n - 1)}{4 - 1} = \frac{4^n - 1}{3} $$

$a_{n,2}$ は、これら $n$ 個の整数から異なる2個を選んで掛けたものの和であるから、対称式の性質より以下の関係が成り立つ。

$$ (S_1)^2 = S_2 + 2 a_{n,2} $$

したがって、$a_{n,2}$ は次のように求められる。

$$ \begin{aligned} a_{n,2} &= \frac{1}{2} \left\{ (S_1)^2 - S_2 \right\} \\ &= \frac{1}{2} \left\{ (2^n - 1)^2 - \frac{4^n - 1}{3} \right\} \\ &= \frac{1}{2} \left( 4^n - 2 \cdot 2^n + 1 - \frac{4^n - 1}{3} \right) \\ &= \frac{1}{2} \left( \frac{3 \cdot 4^n - 6 \cdot 2^n + 3 - 4^n + 1}{3} \right) \\ &= \frac{2 \cdot 4^n - 6 \cdot 2^n + 4}{6} \\ &= \frac{4^n - 3 \cdot 2^n + 2}{3} \end{aligned} $$

因数分解すると以下のようになる。

$$ a_{n,2} = \frac{(2^n - 1)(2^n - 2)}{3} $$

(2)

与えられた整式 $f_n(x) = 1 + a_{n,1}x + a_{n,2}x^2 + \cdots + a_{n,n}x^n$ の $x^k$ の係数 $a_{n,k}$ は、$2^0, 2^1, \dots, 2^{n-1}$ から異なる $k$ 個を選んで掛けた和である。これは、次のように因数分解された整式を展開した結果と一致する。

$$ f_n(x) = (1 + 2^0 x)(1 + 2^1 x) \cdots (1 + 2^{n-1} x) = \prod_{m=0}^{n-1} (1 + 2^m x) $$

この表現を用いると、$f_{n+1}(x)$ は次のように表される。

$$ f_{n+1}(x) = \prod_{m=0}^{n} (1 + 2^m x) = \left( \prod_{m=0}^{n-1} (1 + 2^m x) \right) (1 + 2^n x) = f_n(x)(1 + 2^n x) $$

したがって、$\frac{f_{n+1}(x)}{f_n(x)}$ は次のようになる。

$$ \frac{f_{n+1}(x)}{f_n(x)} = 1 + 2^n x $$

また、$f_n(2x)$ は次のように変形できる。

$$ f_n(2x) = \prod_{m=0}^{n-1} (1 + 2^m \cdot 2x) = \prod_{m=0}^{n-1} (1 + 2^{m+1} x) = \prod_{m=1}^{n} (1 + 2^m x) $$

一方、$f_{n+1}(x)$ は次のように分けることもできる。

$$ f_{n+1}(x) = \prod_{m=0}^{n} (1 + 2^m x) = (1 + 2^0 x) \prod_{m=1}^{n} (1 + 2^m x) = (1 + x) f_n(2x) $$

したがって、$\frac{f_{n+1}(x)}{f_n(2x)}$ は次のようになる。

$$ \frac{f_{n+1}(x)}{f_n(2x)} = 1 + x $$

(3)

(2) で得られた2つの関係式を用いる。便宜上、$a_{n,0} = 1$ とする。

まず、$f_{n+1}(x) = (1 + 2^n x) f_n(x)$ を展開して係数を比較する。

$$ \sum_{k=0}^{n+1} a_{n+1,k} x^k = (1 + 2^n x) \sum_{k=0}^{n} a_{n,k} x^k $$

右辺を展開すると、次のようになる。

$$ \sum_{k=0}^{n} a_{n,k} x^k + \sum_{k=0}^{n} a_{n,k} 2^n x^{k+1} $$

両辺の $x^{k+1}$ の係数を比較すると、次の漸化式が得られる。

$$ a_{n+1, k+1} = a_{n, k+1} + a_{n, k} 2^n \quad \cdots \text{①} $$

次に、$f_{n+1}(x) = (1 + x) f_n(2x)$ を展開して係数を比較する。

$$ \sum_{k=0}^{n+1} a_{n+1,k} x^k = (1 + x) \sum_{k=0}^{n} a_{n,k} (2x)^k $$

右辺を展開すると、次のようになる。

$$ \sum_{k=0}^{n} a_{n,k} 2^k x^k + \sum_{k=0}^{n} a_{n,k} 2^k x^{k+1} $$

両辺の $x^{k+1}$ の係数を比較すると、次の漸化式が得られる。

$$ a_{n+1, k+1} = a_{n, k+1} 2^{k+1} + a_{n, k} 2^k \quad \cdots \text{②} $$

$\frac{a_{n+1, k+1}}{a_{n,k}}$ を求めるために、①と②から $a_{n, k+1}$ を消去する。

①より、$a_{n, k+1} = a_{n+1, k+1} - a_{n, k} 2^n$ である。これを②に代入する。

$$ a_{n+1, k+1} = (a_{n+1, k+1} - a_{n, k} 2^n) 2^{k+1} + a_{n, k} 2^k $$

展開して整理する。

$$ a_{n+1, k+1} = a_{n+1, k+1} 2^{k+1} - a_{n, k} 2^{n+k+1} + a_{n, k} 2^k $$

$$ a_{n+1, k+1} (2^{k+1} - 1) = a_{n, k} (2^{n+k+1} - 2^k) $$

右辺を $a_{n,k} 2^k$ でくくる。

$$ a_{n+1, k+1} (2^{k+1} - 1) = a_{n, k} 2^k (2^{n+1} - 1) $$

両辺を $a_{n,k} (2^{k+1} - 1)$ で割る。

$$ \frac{a_{n+1, k+1}}{a_{n, k}} = \frac{2^k (2^{n+1} - 1)}{2^{k+1} - 1} $$

解説

本問は、複数の数の積の和が、特定の多項式（母関数）の係数として表されるという事実（基本対称式と方程式の係数の関係）に気づけるかどうかが鍵となる。

(1) は対称式の公式を用いても容易に計算できるが、(2) 以降は母関数 $f_n(x) = \prod_{m=0}^{n-1} (1 + 2^m x)$ の導入が不可欠である。 (3) は、(2) で求めた2種類の実用的な関係式（一方は最高次側の要因を取り出し、もう一方は定数項側の要因を取り出す操作に相当する）から係数比較を行い、2つの漸化式を立てるという典型的な手法を用いている。係数比較の際は、添字のズレに注意して立式することが重要である。