2020年度東大理系第4問

東大2020年度理系第4問

問題．

$n, k$ を， $1\leqq k\leqq n$ を満たす整数とする． $n$ 個の整数
$2^m\quad(m=0, 1, 2, \ldots\ldots, n-1)$
から異なる $k$ 個を選んでそれらの積をとる． $k$ 個の整数の選び方すべてに対しこのように積をとることにより得られる ${}_n\mathrm{C}_k$ 個の整数の和を $a_{n, k}$ と置く．例えば，
$a_{4, 3} = 2^0\cdot2^1\cdot2^2+2^0\cdot2^1\cdot2^3+2^0\cdot2^2\cdot2^3+2^1\cdot2^2\cdot2^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+\cdots\cdots+a_{n,n}x^n$
を考える． $\frac{f_{n+1}(x)}{f_n(x)}$ と $\frac{f_{n+1}(x)}{f_n(2x)}$ を $x$ についての整式として表せ．

(3) $\frac{a_{n+1, k+1}}{a_{n, k}}$ を $n, k$ で表せ．

(2)ができればあとはあまり難しくないです．解と係数の関係や組み合わせ(2項定理)の考え方の応用という感じの問題です．

解答例．

(1)

$a_{n, 1}=2^0+2^1+\cdots+2^{n-1}$ を2乗すると，

$a_{n, 1}^2=\sum_{i=0}^{n-1}(2^i)^2 + 2a_{n, 2}.$

ここで，

\begin{align*}
a_{n, 1}&= \sum_{i=0}^{n-1}2^i\\
&= 2^n-1
\end{align*}

また，

\begin{align*}
\sum_{i=0}^{n-1} (2^i)^2 &= \sum_{i=0}^{n-1} 4^i\\
\frac{1}{3}(4^n-1)
\end{align*}

なので，

\begin{align*}
a_{n, 2} &= \frac{1}{2}\left\{(2^n-1)^2-\frac{1}{3}(4^n-1)\right\}\\
&= \frac{1}{3}(4^n-3\cdot 2^n+2)\\
&= \frac{1}{3}(2^n-1)(2^n-2).
\end{align*}

(2) $a_{n, k}$ は $2^0, 2^1, \ldots, 2^{n-1}$ から異なる $k$ 個を選んで積をとったものの和なので，

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

と書ける．よって，

\begin{align*}
\frac{f_{n+1}(x)}{f_n(x)} &= \frac{(1+x)(1+2x)\cdots(1+2^{n-1}x)(1+2^nx)}{(1+x)(1+2x)\cdots(1+2^{n-1}x)}\\
&= 1+2^nx\\
\frac{f_{n+1}(x)}{f_n(2x)} &= \frac{(1+x)(1+2x)\cdots(1+2^{n-1}x)(1+2^nx)}{(1+2x)(1+4x)\cdots(1+2^nx)}\\
&= 1+x.
\end{align*}

(3) (2)より，

$f_{n+1}(x)=(1+2^nx)f_n(x)=(1+x)f_n(2x).$

ここに， $f_n(x)=1+a_{n,1}x+a_{n,2}x^2+\cdots+a_{n,n}x^n$ を代入して係数を比較する．

\begin{align*}
(1+2^nx)f_n(x) &= 1+(2^n+a_{n,1})x+(2^na_{n,1}+a_{n,2})x^2+\cdots\\
&\quad\quad\quad\quad+(2^na_{n, n-1}+a_{n,n})x^n+2^na_{n,n}x^{n+1}
\end{align*}

また， $f_n(2x)=1+2a_{n,1}x+2^2a_{n,2}x^2+\cdots+2^na_{n,n}x^n$ なので，

\begin{align*}
(1+x)f_n(2x) &= 1+(1+2a_{n,1})x+(2a_{n,1}+2^2a_{n,2})x^2+\cdots\\
&\quad\quad\quad\quad+(2^{n-1}a_{n,n-1}+2^na_{n,n})x^n+2^na_{n,n}x^{n+1}
\end{align*}

よって， $a_{n,0}=1, a_{n, n+1}=0$ とおいて，