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

問題編

問題

　$n,k$ を、 $1\leqq k\leqq n$ を満たす整数とする。 $n$ 個の整数\[ 2^m\quad(m=0,1,2,\cdots,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+a_{n,n}x^n \]を考える。 $\dfrac{f_{n+1}(x)}{f_n(x)}$ と $\dfrac{f_{n+1}(x)}{f_n(2x)}$ を $x$ についての整式として表せ。

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

考え方

見るからに大変そうですが、実際大変です。

(1)は $a_{n,k}$ の定義がきちんと把握できていたら、計算を頑張るだけです。

(2)は手がかりが少ないですね。ただ、問題文自体をヒントとして使ってみましょう。 $f_{n+1}(x)$ は $n+1$ 次式で $f_n(x)$ は $n$ 次式です。なので、割ったものが整式となるなら、1次式になるはずです。しかも、定数項は $1$ になることがわかるので、どちらも、 $ax+1$ の形の答えになることがわかります。あとは $x$ の係数を求めるだけです。 $f_{n+1}(x)$ の $x^k$ の項と、 $f_n(x)$ の $x^{k-1}$ と $x^k$ の項との関係を考えればいいことがわかります。

(3)は(2)の結果を使います。(2)で2つの式が得られるので、文字を一つ消すことができます。

---

解答編

問題

　$n,k$ を、 $1\leqq k\leqq n$ を満たす整数とする。 $n$ 個の整数\[ 2^m\quad(m=0,1,2,\cdots,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}$ を求めよ。

解答

(1)
$2^m$ $(m=0,1,2,\cdots,n-1)$ から異なる2個をとって積を計算し、すべて足し合わせたものが $a_{n,2}$ である。よって、 $2^i\cdot 2^j$ （ $i,j$ は整数で、 $0\leqq i,j\leqq n-1$ ）をすべて足し合わせて、 $i=j$ のものを引き、2で割れば $a_{n,2}$ が求められる。

\begin{eqnarray} 2a_{n,2} &=& \sum_{i=0}^{n-1}\sum_{j=0}^{n-1} 2^i\cdot 2^j -\sum_{i=0}^{n-1} 2^i\cdot 2^i \\[5pt] &=& \sum_{i=0}^{n-1}2^i \sum_{j=0}^{n-1}\cdot 2^j -\sum_{i=0}^{n-1} 4^i \\[5pt] &=& (2^n-1)(2^n-1) -\frac{4^n-1}{4-1} \\[5pt] &=& 4^n-2^{n+1}+1 -\frac{4^n-1}{3} \\[5pt] &=& \frac{2\cdot 4^n}{3}-2^{n+1}+\frac{4}{3} \\[5pt] \end{eqnarray}なので、\[ a_{n,2}=\frac{4^n}{3}-2^n+\frac{2}{3} \]となる。 （終）

解答編　つづき

問題

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

解答

(2)
$k$ は $1\leqq k\leqq n+1$ を満たす整数とする。また、 $a_{n,0}=1$, $a_{n,n+1}=0$ と定める。

$a_{n+1,k}$ は、 $2^m$ $(m=0,1,2,\cdots,n)$ から異なる $k$ 個をとって積を計算し、すべて足し合わせたものである。

このとき、選んだ $k$ 個の中に $2^n$ が含まれているものだけをすべて足し合わせると、 $2^m$ $(m=0,1,2,\cdots,n-1)$ から異なる $k-1$ 個をとって積を計算し、すべて足し合わせたものに $2^n$ を掛けたものと一致するため、 $2^n a_{n,k-1}$ となる。これは、 $k=1$ のときも成り立つ。

また、選んだ $k$ 個の中に $2^n$ が含まれていないものだけをすべて足し合わせると、 $2^m$ $(m=0,1,2,\cdots,n-1)$ から異なる $k$ 個をとって積を計算し、すべて足し合わせたものと一致するため、 $a_{n,k}$ となる。これは $k=n+1$ のときも成り立つ。

以上から、\[ a_{n+1,k}=2^n a_{n,k-1}+a_{n,k} \quad \cdots (*) \]が成り立つ。

このことから、
\begin{eqnarray} & & f_{n+1}(x) \\[5pt] &=& 1+a_{n+1,1}x+a_{n+1,2}x^2+\cdots+a_{n+1,n+1}x^{n+1} \\[5pt] &=& a_{n,0}+(2^n a_{n,0}+a_{n,1})x+(2^n a_{n,1}+a_{n,2})x^2 \\ & & +\cdots +(2^n a_{n,n-1}+a_{n,n})x^n +(2^n a_{n,n}+a_{n,n+1})x^{n+1} \\[5pt] &=& a_{n,0}+a_{n,1}x+a_{n,2}x^2+\cdots+a_{n,n}x^n \\ & & +2^nx (a_{n,0}+a_{n,1}x+a_{n,2}x^2+\cdots+a_{n,n}x^n) \\[5pt] &=& (1+2^nx)(a_{n,0}+a_{n,1}x+a_{n,2}x^2+\cdots+a_{n,n}x^n) \\[5pt] &=& (1+2^nx)f_n(x) \\[5pt] \end{eqnarray}となるので、 $\dfrac{f_{n+1}(x)}{f_n(x)}=1+2^nx$ となる。

$n=1$ のときは $a_{1,1}=1$ であることから $f_1(x)=1+x$ である。また、先ほど求めた式を繰り返し用いると
\begin{eqnarray} & & f_n(x) \\[5pt] &=& (1+2^{n-1}x)(1+2^{n-2}x)(1+2^{n-3}x)\cdots (1+2^1x) f_1(x) \\[5pt] &=& \prod_{k=0}^{n-1}(1+2^k x) \\[5pt] \end{eqnarray}となることがわかる。なお、 $\prod$ はすべての項を掛けたもの（総乗）を表す。

これより、
\begin{eqnarray} f_n(2x) &=& \prod_{k=0}^{n-1}(1+2^k \cdot 2x) \\[5pt] &=& \prod_{k=1}^{n}(1+2^k x) \\[5pt] \end{eqnarray}なので \begin{eqnarray} \frac{f_{n+1}(x)}{f_n(x)} &=& \frac{ \prod_{k=0}^{n}(1+2^k x) }{ \prod_{k=1}^{n}(1+2^k x) } \\[5pt] &=& 1+2^0x \\[5pt] &=& 1+x \\[5pt] \end{eqnarray}と表すことができる。

（終）

解答編　つづき

問題

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

(3)
(2)の $(*)$ より、 $a_{n+1,k}=2^n a_{n,k-1}+a_{n,k}$ が成り立つので、\[ a_{n+1,k+1}=2^n a_{n,k}+a_{n,k+1} \]が成り立つ。

また、(2)の最後の結果から
\begin{eqnarray} f_{n+1}(x) &=& (1+x)f_n(2x) \\[5pt] &=& (1+x) (a_{n,0}+a_{n,1}2x+a_{n,2}2^2x^2+\cdots+a_{n,n}2^nx^n) \\[5pt] \end{eqnarray}なので、 $x^{k+1}$ の項を比較すると\[ a_{n+1,k+1}=2^{k+1} a_{n,k+1} +2^k a_{n,k} \]が成り立つ。

よって
\begin{eqnarray} 2^n a_{n,k}+a_{n,k+1} &=& 2^{k+1} a_{n,k+1} +2^k a_{n,k} \\[5pt] (1-2^{k+1})a_{n,k+1} &=& (2^k-2^n) a_{n,k} \\[5pt] a_{n,k+1} &=& \frac{2^n-2^k}{2^{k+1}-1} a_{n,k} \\[5pt] \end{eqnarray}となる。これより、 \begin{eqnarray} \frac{a_{n+1,k+1} }{a_{n,k} } &=& \frac{2^n a_{n,k}+a_{n,k+1} }{a_{n,k} } \\[5pt] &=& 2^n +\frac{2^n-2^k}{2^{k+1}-1} \\[5pt] &=& \frac{2^{n+k+1}-2^n+2^n-2^k}{2^{k+1}-1} \\[5pt] &=& \frac{2^{n+k+1}-2^k}{2^{k+1}-1} \\[5pt] \end{eqnarray}と表すことができる。

（終）