東大 2020年前期理系第4問(2/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$ で表せ。

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

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

整式 $f_n(x)$ の定義により、
\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 \tag{2.4}
\end{equation}が得られます。
ここで、 $2^k a_{n,k}$ に注目します。
$a_{n,k}$ は $k$ 個の $2^m$ の積の総和です。 $2^k$ 倍すると、 $2^m$ は全て $2^{m+1}$ になります。これらは全て $a_{n+1,k}$ に含まれます。
不足しているのは、 $2^0 \ (=1)$ を必ず含み、 $2^1, \cdots , 2^n$ から $k -1$ 個を選んで積をとったものです。
$2^k$ を括り出すと、残るのは $2^0, \cdots , 2^{n -1}$ から $k -1$ 個を選んで積をとったものになります。
すなわち、
\begin{equation}
2^k a_{n,k} = a_{n+1,k} - 2^{k -1} a_{n,k -1}
\end{equation}が成り立ちます。式を書き換えると、
\begin{equation}
a_{n+1,k} = 2^k a_{n,k} + 2^{k -1} a_{n,k -1} \tag{2.5}
\end{equation}です。なお、
\begin{eqnarray}
a_{n+1,1} &=& 2a_{n,1} +1 \tag{2.6} \\
a_{n+1,n+1} &=& 2^n a_{n,n} \tag{2.3}
\end{eqnarray}です。*1

式(2.4)と式(2.3), (2.5), (2.6)を組合せます。
\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 + (2a_{n,1} + 1)x + (2^2 a_{n,2} + 2a_{n,1})x^2 + \cdots \\
&& + (2^n a_{n,n} + 2^{n -1} a_{n,n -1})x^n + 2^n a_{n,n} x^{n+1} \\
&=& (1 + 2a_{n,1}x + 2^2 a_{n,2}x^2 + \cdots + 2^n a_{n,n}x^n) \\
&& + x(1 + 2a_{n,1}x + \cdots + 2^{n -1} a_{n,n -1}x^{n -1} + 2^n a_{n,n}x^n) \\
&=& f_n(2x) + x \, f_n(2x)
\end{eqnarray}を得ます。
よって、
\begin{equation}
\frac{f_{n+1}(x)}{f_n(2x)} = 1 + x
\end{equation}です。

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

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