東京大学 2020年度文理共通数学文科第4問・理科第4問解答・解説

問題

$n$ ， $k$ を， $1 ≦ k ≦ n$ を満たす整数とする。 $n$ 個の整数

2^{m} (m = 0, 1, 2, \dots\dots, n - 1)

から異なる $k$ 個を選んでそれらの積をとる。 $k$ 個の整数の選び方すべてに対しこのように積をとることにより得られる $_{n} C_{k}$ 個の整数の和を $a_{n, k}$ とおく。例えば，

a_{4, 3} = 2^{0} \cdot 2^{1} \cdot 2^{2} + 2^{0} \cdot 2^{1} \cdot 2^{3} + 2^{0} \cdot 2^{2} \cdot 2^{3} + 2^{1} \cdot 2^{2} \cdot 2^{3} = 120

である。

(1) 2以上の整数 $n$ に対し， $a_{n, 2}$ を求めよ。

(2) 1以上の整数 $n$ に対し， $x$ についての整式

f_{n} (x) = 1 + a_{n, 1} x + a_{n, 2} x^{2} + \dots\dots + a_{n, n} x^{n}

を考える。 $\frac{f _{n + 1} ( x )}{f _{n} ( x )}$ と $\frac{f _{n + 1} ( x )}{f _{n} ( 2 x )}$ を $x$ についての整式として表せ。

(3) $\frac{a _{n + 1, k + 1}}{a _{n, k}}$ を $n$ ， $k$ で表せ。

出典：東京大学 2020年度前期日程第2次学力試験文理共通文科第4問・理科第4問

方針

解法1（母関数を2通りに比較する方法）

$a_{n, k}$ を整式 $f_{n} (x)$ の係数として捉える。(1)は平方和を引いて求め、(2)は $f_{n}$ を積に分解する。(3)は $f_{n + 1} (x)$ を $(1 + 2^{n} x) f_{n} (x)$ と $(1 + x) f_{n} (2 x)$ の2通りに表し、係数比較で不要な比を消去する。

解法2（明示公式を帰納的に作る方法）

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

解答

解法1（母関数を2通りに比較する方法）

(1)

a_{n, 2} = 0 ≦ i < j ≦ n - 1 \sum 2^{i + j} .

全体の和の平方から同じ項どうしの積を除くと

a_{n, 2} = \frac{1}{2} {(1 + 2 + \dots + 2^{n - 1})^{2} - (1 + 2^{2} + \dots + 2^{2 n - 2})} .

等比数列の和を代入して

a_{n, 2} = \frac{1}{2} {(2^{n} - 1)^{2} - \frac{4 ^{n} - 1}{3}} = \frac{4 ^{n} - 3 \cdot 2 ^{n} + 2}{3} .

(2)

各因子から定数項または $2^{m} x$ を選んで展開すると、 $x^{k}$ の係数がちょうど $a_{n, k}$ になる。よって

f_{n} (x) = (1 + x) (1 + 2 x) \dots (1 + 2^{n - 1} x) .

したがって

f_{n + 1} (x) = (1 + 2^{n} x) f_{n} (x)

および

f_{n + 1} (x) = (1 + x) f_{n} (2 x)

であるから、

\frac{f _{n + 1} ( x )}{f _{n} ( x )} = 1 + 2^{n} x, \frac{f _{n + 1} ( x )}{f _{n} ( 2 x )} = 1 + x .

(3)

第1の恒等式で $x^{k + 1}$ の係数を比較すると

a_{n + 1, k + 1} = a_{n, k + 1} + 2^{n} a_{n, k} .

第2の恒等式からは

a_{n + 1, k + 1} = 2^{k + 1} a_{n, k + 1} + 2^{k} a_{n, k} .

両式を引いて

(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} .

これを最初の式へ戻せば

\frac{a _{n + 1, k + 1}}{a _{n, k}} = 2^{n} + \frac{2 ^{n} - 2 ^{k}}{2 ^{k + 1} - 1} = \frac{2 ^{k} ( 2 ^{n + 1} - 1 )}{2 ^{k + 1} - 1} .

$k = n$ の場合も右辺は $2^{n}$ となり、式はそのまま成り立つ。

解法2（明示公式を帰納的に作る方法）

(1)

大きい方の指数を $j$ とすると

a_{n, 2} = j = 1 \sum n - 1 2^{j} (1 + 2 + \dots + 2^{j - 1}) = j = 1 \sum n - 1 (4^{j} - 2^{j}) = \frac{4 ^{n} - 4}{3} - (2^{n} - 2) = \frac{4 ^{n} - 3 \cdot 2 ^{n} + 2}{3} .

(2)

選んだ指数を係数として記録するため

f_{n} (x) = (1 + x) (1 + 2 x) \dots (1 + 2^{n - 1} x) .

よって直ちに

\frac{f _{n + 1} ( x )}{f _{n} ( x )} = 1 + 2^{n} x, \frac{f _{n + 1} ( x )}{f _{n} ( 2 x )} = 1 + x .

(3)

$k$ 個を選ぶとき $2^{n - 1}$ を選ばない場合と選ぶ場合に分けると

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

この漸化式から数学的帰納法により

a_{n, k} = 2^{k (k - 1) /2} \frac{( 2 ^{n} - 1 ) ( 2 ^{n - 1} - 1 ) \dots ( 2 ^{n - k + 1} - 1 )}{( 2 ^{k} - 1 ) ( 2 ^{k - 1} - 1 ) \dots ( 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} .

この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} .

東京大学 2020年度文理共通数学 文科第4問・理科第4問

問題

方針

解法1（母関数を2通りに比較する方法）

解法2（明示公式を帰納的に作る方法）

解答

解法1（母関数を2通りに比較する方法）

(1)

(2)

(3)

解法2（明示公式を帰納的に作る方法）

(1)

(2)

(3)

東京大学 2020年度
文理共通数学文科第4問・理科第4問