🏠 Home / 東京大学 / 東大理系

東京大学 理系 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}と表すことができる。

(終)

関連するページ

YouTubeもやってます

チャンネル登録はコチラから (以下は、動画のサンプルです)
慶應義塾大学薬学部2024年度数学第1問5 同志社大学文系2024年度数学第1問3 昭和大学医学部I期2024年度数学第2問 兵庫医科大学2024年度数学第3問 共通テスト2B2024年度第3問2のヒントについて 久留米大学医学部推薦2024年度数学第4問