東大 2020年前期理系第4問(1/3)

$n,k$ を、 $1 \leqq k \leqq n$ を満たす整数とする。 $n$ 個の整数
\begin{equation}
2^m \quad (m=0,1,2, \cdots , n -1)
\end{equation}から異なる $k$ 個を選んでそれらの積をとる。 $k$ 個の整数の選び方すべてに対し、このように積をとることにより得られる ${}_n C_k$ 個の整数の和を $a_{n,k}$ とおく。例えば、
\begin{equation}
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
\end{equation}である。
(1) 2以上の整数 $n$ に対し、 $a_{n,2}$ を求めよ。
(2) 1以上の整数 $n$ に対し、 $x$ の整式
\begin{equation}
f_n(x) = 1 + a_{n,1}x + a_{n,2}x^2 + \cdots + a_{n,n}x^n
\end{equation}を考える。 $\displaystyle \frac{f_{n+1}(x)}{f_n(x)}$ と $\displaystyle \frac{f_{n+1}(x)}{f_n(2x)}$ を $x$ についての整式で表せ。
(3) $\displaystyle \frac{a_{n+1,k+1}}{a_{n,k}}$ を $n,k$ で表せ。

小問(1)の見通し

文章が長い問題です。さらに文字の定義が物凄いことになっています。
その中でも、小問(1)は「軽い」ジャブなのでしょう。
とは言え、 $a_{n,2}$ を直接求めることは不可能です。直接求めることができないとなれば、漸化式を考えていくことになります。

小問(1)の答案

$a_{n,2}$ は $2^0, \cdots , 2^{n -1}$ から異なる2個を選んで積をとったものの総和、
$a_{n+1,2}$ は $2^0, \cdots , 2^n$ から異なる2個を選んで積をとったものの総和です。
$a_{n+1,2}$ には $a_{n,2}$ の全ての積が含まれています。余っているのは、 $2^n$ と $2^0, \cdots , 2^{n -1}$ との積です。
したがって、
\begin{eqnarray}
a_{n+1,2} &=& a_{n,2} + (2^0 + 2^1 + \cdots + 2^{n -1})\, 2^n \\
&=& a_{n,2} + (2^n - 1)\, 2^n
\end{eqnarray}となります。
整理して、添字を減らしていきます。併せて $a_{2,2}$ も求めておきます。
\begin{eqnarray}
a_{n,2} &=& a_{n -1,2} + 4^{n -1} - 2^{n -1} \\
a_{n -1,2} &=& a_{n -2,2} + 4^{n -2} - 2^{n -2} \\
& \vdots & \\
a_{3,2} &=& a_{2,2} + 4^2 - 2^2 \\
a_{2,2} &=& 2 \qquad (\because a_{2,2} = 2^0 \cdot 2^1 = 2)
\end{eqnarray}
これら $n -1$ 本の式を辺々相加えると、 $a_{n,2}$ を得ます。
\begin{eqnarray}
a_{n,2} &=& \frac{4^2(4^{n -2} -1)}{3} - 2^2(2^{n -2} -1) + 2 \\
&=& \frac{4^n}{3} - 2^n + \frac{2}{3}
\end{eqnarray}

小問(2)の見通し

小問(1)に輪をかけて凄まじくなっています。
定義より、 $f_{n+1}(x)$ は $x$ の $n+1$ 次式で、 $f_n(x), \ f_n(2x)$ は $n$ 次式です。
本当に整式の比が整式で表すことができるのか？　と訝ってしまいます。
$f_{n+1}(x)$ と $f_n(x), \ f_n(2x)$ を繋ぐものがあればハッピーです。
やはり、 $a_{n+1,k}$ と $a_{n,k}$ を繋ぐもの、つまり漸化式を作ることになります。
また、
\begin{equation}
f_n(2x) = 1 + 2a_{n,1}x + 2^2 a_{n,2}x^2 + \cdots + 2^n a_{n,n}x^n
\end{equation}なので、 $2^k a_{n,k}$ と $a_{n+1,k}$ を繋ぐ関係があれば、筋道は立ちそうです。

小問(2)の答案(前半)

$a_{n+1,k}$ は、 $a_{n,k}$ の要素を全て含んでいます。
余っているのは、 $2^n$ を必ず含み、 $2^0, \cdots , 2^{n -1}$ から $k -1$ 個を選んで積をとったものです。
すなわち、
\begin{equation}
a_{n+1,k} = a_{n,k} + 2^n a_{n, k -1} \tag{2.1}
\end{equation}が成り立ちます。
なお、
\begin{eqnarray}
a_{n+1,1} &=& a_{n,1} + 2^n \tag{2.2} \\
a_{n+1,n+1} &=& 2^n a_{n,n} \tag{2.3}
\end{eqnarray}です。*1 *2

式(2.1), (2.2), (2.3)を用いると、
\begin{eqnarray}
f_{n+1,k}(x) &=& 1 + a_{n+1,1}x + a_{n+1,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^n a_{n,1})x^2 + \cdots \\
&&+ (a_{n,n} + 2^n a_{n,n -1})x^n + 2^n a_{n,n} x^{n+1} \\
&=& (1 + a_{n,1}x + a_{n,2}x^2 + \cdots + a_{n,n}x^n) \\
&&+ 2^n x(1 + a_{n,1}x + \cdots + a_{n,n -1}x^{n -1} + a_{n,n}x^n) \\
&=& f_n(x) + 2^n x \, f_n(x)
\end{eqnarray}を得ます。
よって、
\begin{equation}
\frac{f_{n+1}(x)}{f_n(x)} = 1 + 2^n x
\end{equation}です。

続きます。
東大 2020年前期理系第4問(2/3) - 数式で独楽する

*1:\begin{eqnarray} a_{n,1} &=& 2^0 + 2^1 + \cdots + 2^{n -1} \\ a_{n+1,1} &=& 2^0 + 2^1 + \cdots + 2^{n -1} + 2^n \end{eqnarray}です。

*2:\begin{eqnarray} a_{n,n} &=& 2^0 \cdot 2^1 \cdot \cdots \cdot 2^{n -1} \\ a_{n+1,n+1} &=& 2^0 \cdot 2^1 \cdot \cdots \cdot 2^{n -1} \cdot 2^n \end{eqnarray}です。