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

今回は、東京大学理系数学（2020年 第4問）の解説をしたいと思います。

問題

　$n,k$ を，$1\leqq k\leqq n$ を満たす整数とする。$n$ 個の整数
$$2^m \quad (m=0,1,2,\cdots\cdots,n-1)$$から異なる $k$ 個を選んでそれらの積とる。$k$ 個の整数の選び方すべてに対しこのように積をとることにより得られる ${}_n\mathrm{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$$である。

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

⑵　$1$ 以上の整数 $n$ に対し，$x$ についての整式
$$f_n(x) = 1+a_{n,1}x+a_{n,2}x^2+\cdots\cdots+a_{n,n}x^n$$を考える。$\dfrac{f_{n+1}(x)}{f_n(x)}$ と $\dfrac{f_{n+1}(x)}{f_n(2x)}$ を $x$ についての整式として表せ。

⑶　$\dfrac{a_{n+1,k+1}}{a_{n,k}}$ を $n,k$ で表せ。

（東京大学）

解答

⑴

解法1（ $2$ 乗の展開を考える）

$$\begin{eqnarray}
&& (2^0 + 2^1 + 2^2 + \cdots + 2^{n-1})^2 \\
&=& (2^0)^2 + (2^1)^2 + (2^2)^2 + \cdots (2^{n-1})^2 + 2a_{n,2} \\
&=& (2^2)^0 + (2^2)^1 + (2^2)^2 + \cdots (2^2)^{n-1} + 2a_{n,2}
\end{eqnarray}$$より
$$\begin{align}
a_{n,2} &= \dfrac{1}{2} \left\{ \left(\dfrac{2^n-1}{2-1}\right)^2 – \ \dfrac{(2^2)^n-1}{2^2-1} \right\} \\
&= \dfrac{1}{2} \cdot \dfrac{3(2^n-1)^2 \ – \ (2^n+1)(2^n-1)}{3} \\
&= \dfrac{1}{2} \cdot \dfrac{(2^n-1)(2^{n+1}-4)}{3} \\
&= \boldsymbol{\dfrac{(2^n-1)(2^n-2)}{3}}
\end{align}$$

解法2（ $\Sigma$ で計算）

$a_{n,2}$ は $2^p2^q$（ $p,q$ は $0\leqq p \leqq n-1, \ $$0\leqq q \leqq n-1$ を満たす整数）の総和から $p=q$ の場合を引いて、$2$ で除したものに等しく
$$\begin{align}
a_{n,2} &= \dfrac{1}{2}\left( \displaystyle\sum_{p=0}^{n-1} \displaystyle\sum_{q=0}^{n-1} 2^p2^q \ – \ \displaystyle\sum_{p=0}^{n-1} 2^p2^p \right) \\
&= \dfrac{1}{2}\left\{ \displaystyle\sum_{p=0}^{n-1} 2^p \displaystyle\sum_{q=0}^{n-1} 2^q \ – \ \displaystyle\sum_{p=0}^{n-1} (2^2)^p \right\} \\
&= \dfrac{1}{2} \left\{ \left(\dfrac{2^n-1}{2-1}\right)^2 – \ \dfrac{(2^2)^n-1}{2^2-1} \right\} \\
&= \dfrac{1}{2} \cdot \dfrac{3(2^n-1)^2 \ – \ (2^n+1)(2^n-1)}{3} \\
&= \dfrac{1}{2} \cdot \dfrac{(2^n-1)(2^{n+1}-4)}{3} \\
&= \boldsymbol{\dfrac{(2^n-1)(2^n-2)}{3}}
\end{align}$$

⑵

解法1（多項式の係数）

多項式 $F_n(x)$ を
$$F_n(x) = (1+x)(1+2x)(1+2^2x)\cdots(1+2^{n-1}x)$$とすると、$F_n(x)$ の $x^k$ の係数は、$2^m \ $$(m=0,1,2,\cdots,n-1)$ から異なる $k$ 個を選んで積をとったものの総和なので $a_{n,k}$ に一致する。

さらに定数項が $1$ なので、$F_n(x)=f_n(x)$ であると分かる。

したがって
$$\begin{alignat}{2}
f_n(x) &= (1+x)&&(1+2x)(1+2^2x)\cdots(1+2^{n-1}x) \\
f_n(2x) &=&&(1+2x)(1+2^2x)\cdots(1+2^{n-1}x)(1+2^nx) \\
f_{n+1}(x) &= (1+x)&&(1+2x)(1+2^2x)\cdots(1+2^{n-1}x)(1+2^{n}x)
\end{alignat}$$より
$$\dfrac{f_{n+1}(x)}{f_n(x)} = \boldsymbol{1+2^nx},\quad \dfrac{f_{n+1}(x)}{f_n(2x)} = \boldsymbol{1+x}$$

解法2（ $a_{n+1,k}$ の和のとり方に着目）

$$\begin{align}
a_{n+1,1} = a_{n,1} + 2^n , \quad a_{n+1,n+1} = 2^na_{n,n}
\end{align}$$が成り立つ。

ここで、$\ell$ を $2\leqq \ell\leqq n$ を満たす整数とする。

$a_{n+1,\ell}$ は「 $2^m \ $$(m=0,1,2,\cdots,n-1)$ から異なる $\ell$ 個を選んで積をとったものの総和」と「 $2^m \ $$(m=0,1,2,\cdots,n-1)$ から異なる $(\ell-1)$ 個を選び、$2^n$ と合わせて $\ell$ 個の整数の積をとったものの総和」の和であるから
$$a_{n+1,\ell} = a_{n,\ell} + 2^na_{n,\ell-1} \quad\cdots\text{①}$$が成り立つ。

よって
$$\begin{align}
f_{n+1}(x) &= 1 + a_{n+1,1}x + a_{n+2,2}x^2 + \cdots + a_{n+1,n}x^n + a_{n+1,n+1}x^{n+1} \\
&= 1 + (a_{n,1} + 2^n)x + (a_{n,2} + 2^na_{n,1})x^2 \\
& \ \quad + \cdots + (a_{n,n} + 2^na_{n,n-1})x^n + 2^na_{n,n}x^{n+1} \\
&= 1 + a_{n,1}x + a_{n,2}x^2 + \cdots + a_{n,n}x^n \\
& \ \quad + 2^nx(1 + a_{n,1}x + \cdots + a_{n,n-1}x^{n-1} + a_{n,n}x^n) \\
&= f_n(x) + 2^nxf_n(x) \\
&= (1+2^nx)f_n(x)
\end{align}$$より
$$\dfrac{f_{n+1}(x)}{f_n(x)} = \boldsymbol{1+2^nx} \quad\cdots\text{②}$$

また、$n=1$ のとき
$$f_1(x) = 1+a_{1,1}x = 1+x$$であるから、②より
$$\begin{align}
f_n(x) &= f_1(x) \cdot \dfrac{f_2(x)}{f_1(x)} \cdot \dfrac{f_3(x)}{f_2(x)} \cdot \cdots \cdot \dfrac{f_n(x)}{f_{n-1}(x)} \\
&= (1+x)(1+2x)(1+2^2x)\cdots(1+2^{n-1}x)
\end{align}$$

よって
$$\begin{alignat}{2}
f_{n+1}(x) &= (1+x) & & (1+2x)(1+2^2x)\cdots(1+2^{n}x) \\
f_n(2x) &= & & (1+2x)(1+2^2x)\cdots(1+2^nx)
\end{alignat}$$であるから
$$\dfrac{f_{n+1}(x)}{f_n(2x)} = \boldsymbol{1+x}$$

⑶

解法1（多項式の係数比較）

$f_{n+1}(x)$ の $x^{k+1}$ の係数が $a_{n+1,k+1}$ である。

また、$f_{n}(x)$ の $x^{k},x^{k+1}$ の係数はそれぞれ $a_{n,k},a_{n,k+1}$ であり、$f_{n}(2x)$ の $x^{k},x^{k+1}$ の係数はそれぞれ $2^ka_{n,k},2^{k+1}a_{n,k+1}$ である。
ただし、$a_{n,n+1}=0$ とする。

⑵より
$$\left\{
\begin{align}
f_{n+1}(x) &= (1+2^nx)f_n(x) \\
f_{n+1}(x) &= (1+x)f_n(2x)
\end{align}
\right.$$であるから、$x^{k+1}$ の係数を比較すると
$$\left\{
\begin{alignat}{2}
a_{n+1,k+1} &= a_{n,k+1}+2^na_{n,k}&\quad &\cdots\text{③}\\
a_{n+1,k+1} &= 2^{k+1}a_{n,k+1}+2^ka_{n,k}& &\cdots\text{④}
\end{alignat}
\right.$$③,④より
$$(2^{k+1}-1)a_{n+1,k+1} = 2^k(2^{n+1}-1)a_{n,k}$$$2^{k+1}-1 \ne 0$ より
$$\dfrac{a_{n+1,k+1}}{a_{n,k}} = \boldsymbol{\dfrac{2^k(2^{n+1}-1)}{2^{k+1}-1}}$$

解法2（ $a_{n+1,k+1}$ の和のとり方に着目）

①で $\ell = k+1$ とすると
$$a_{n+1,k+1} = a_{n,k+1} + 2^na_{n,k} \quad \cdots\text{⑤}$$

また $a_{n+1,k+1}$ は「 $2^m \ $$(m=1,2,\cdots,n)$ から異なる $(k+1)$ 個を選んで積をとったものの総和」と「 $2^m \ $$(m=1,2,\cdots,n)$ から異なる $k$ 個を選び、$2^0$ と合わせて $(k+1)$ 個の整数の積をとったものの総和」の和であるから、$a_{n,k}$ の定義に注意すると
$$a_{n+1,k+1} = 2^{k+1}a_{n,k+1} + 2^ka_{n,k} \quad\cdots\text{⑥}$$が成り立つ。

⑤,⑥より
$$(2^{k+1}-1)a_{n+1,k+1} = 2^k(2^{n+1}-1)a_{n,k}$$$2^{k+1}-1 \ne 0$ より
$$\dfrac{a_{n+1,k+1}}{a_{n,k}} = \boldsymbol{\dfrac{2^k(2^{n+1}-1)}{2^{k+1}-1}}$$

解説

⑴は「解法1」の方法が思いつけば、後の設問の見通しも良くなります。

とは言え、⑵で「解法1」はなかなか思いつきづらいです。$(a+b)^n$ の展開式を考えるときに $k$ 個の $a$ と $(n-k)$ 個の $b$ の積が ${}_n\mathrm{C}_k$ 個あるといったことを考えますが、それと似たような発想で、実にエレガントです。
時間の限られた試験では「解法2」のように解くのが無難かと思います。

⑶は、⑵をヒントとして解いた場合の「解法1」と、⑵を無視した場合の「解法2」があります。⑴,⑵が無くいきなり⑶を出題された場合、「解法2」のような解き方になると思います。

ちなみに本問のように、数列を係数として $1$ つの関数にまとめたものを「母関数ぼかんすう」といいます。今回でいうと、$f_n(x)$ は $a_{n,k}$ の母関数です。
よく知られたものでいえば、$(1+x)^n$ は二項係数 ${}_n\mathrm{C}_k$ の母関数になっています。

まとめ

今回は、東京大学理系数学（2020年 第4問）の解説をしました。