第4問の解説をやってみようと思います。
\(n, k\) を、\(1 \leq k \leq n\) を満たす整数とする。 \(n\) 個の整数
\begin{align*}
2^m (m = 0, 1, 2, ……, n-1)
\end{align*}から異なる \(k\) 個を選んでそれらの積をとる。 \(k\) 個の整数の選び方すべてに対しこのように積をとることにより得られる \(_n \mathrm{C} _k\) 個の整数の和を \(a_{n, k}\) とおく。例えば、
\begin{align*}
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{align*}である。
(1) 2 以上の整数 \(n\) に対し、 \(a_{n, 2}\) を求めよ。
(2) 1 以上の整数 \(n\) に対し、 \(x\) についての整式
\begin{align*}
f_n(x) = 1 + a_{n, 1} x + a_{n, 2} x^2 + …… + a_{n, n} x^n
\end{align*}を考える。 \(\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\) で表せ。
東京大学 2020 理系
解いてみた感想
一番難しいと思います。逆に言うと、これと第6問 (2)の後半以外は標準的なので、試験場では不用意に時間を溶かさずに他の問題をしっかり取りきれるかが重要なんじゃないですかね。
僕は (2) 移行、一番最後に時間余ったらボーナス問題として解くかな…まぁ気づいちゃえばできるけど、試験場では厳しいよなぁという感じ
(1) とりあえず落ち着いて足そう
(1) までは取りたいですよね。愚直に考えますか。\(0 \leq i < j \leq n – 1\) となるように \(i, j\) を選び（選び方が \(_n \mathrm{C} _2\) 通り）、このような \(i, j\) について \(2^i \cdot 2^j\) を足し合わせればよいという感じですね。
\sum_{j = 1}^{n-1} \sum_{i=0}^{j-1} 2^i \cdot 2^j = \sum_{j = 1}^{n-1} (2^j – 1) 2^j \\ = \frac{4^n}{3} – 2^n + \frac{2}{3}
\end{align*}
となります。
(2) 場合分けして漸化式を立てる力
とりあえず、 \(a_{n+1, ?}\) を \(a_{n, ?}\) を使って表すことができれば、 \(f_{n+1} (x)\) と \(f_{n} (x)\) の関係も分かってきそうな気がします。
ということで、定義とにらめっこしながら漸化式を立ててみましょう。
\(a_{n+1, k+1}\) という数について考えてみます。
「n+1 → n で何が変わるか？」を考えて場合分けしてみる
まず、 \(n + 1 \to n\) になると、 \(2^n\) を選ぶ対象に含むかどうかが変わってきます。そこで、これを基準にして場合分けをしてみましょう。（あとで足し合わせる方針）
case1. \(2^n\) を選ぶ場合
このとき、他の \(2^m (m=0, 1, ……, n-1) \) から \(k\) 個を選び、それらの積の総和（つまり \(a_{n, k}\) ）に \(2^n\) をかければよい。
case2. \(2^n\) を選ばない場合
他の \(2^m (m=0, 1, ……, n-1) \) から \(k+1\) 個を選び、それらの積の総和をとればよい（つまり \(a_{n, k+1}\) ）
case1, case2 は排反で場合分けはこれですべてなので、結局
$$ a_{n+1, k+1} = 2^n a_{n, k} + a_{n, k+1} $$
となります。
\(n\) を1つ減らせたので、あとはこれを使って \(f_{n+1} (x)\) をゴニョゴニョして \(f_{n} (x)\) で表せそうな気がする…
というわけで、頑張ってゴニョゴニョしてみましょう。
f_{n+1} (x) & = 1 + a_{n+1, 1} x + a_{n+1, 2} x^2 + …… + a_{n+1, n+1} x^{n+1} \\
& = 1 + (2^{n} a_{n, 0} + a_{n, 1}) x + (2^{n} a_{n, 1} + a_{n, 2}) x^2 + …… + (2^{n} a_{n, n} + a_{n, n+1}) x^{n+1} \\
& = 1 + a_{n, 1} x + a_{n, 2} x^2 + …… + a_{n, n} x^n + 2^{n} x (a_{n, 0} + a_{n, 1} x + a_{n, 2} x^2 + …… + a_{n, n} x^n ) \\
& = (1 + 2^{n} x) (1 + a_{n, 1} x + a_{n, 2} x^2 + …… + a_{n, n} x^n) \\
& = (1 + 2^{n} x) f_n (x)
\end{align*}
わ〜〜〜やったぁ〜〜〜報われた〜〜〜 😇🎉
ということで、
$$ \frac{f_{n+1}(x)}{f_n(x)} = 1 + 2^n x $$
が得られます。
漸化式から一般項を求める
そしてそして、漸化式が分かったので一般項を求めてみましょう。
$$ \frac{f_{n+1}(x)}{f_n(x)} = 1 + 2^n x $$
より、
f_{n} (x) & = \frac{f_{n}(x)}{f_{n-1}(x)} \cdot \frac{f_{n-1}(x)}{f_{n-2}(x)} …… \cdot \frac{f_{2}(x)}{f_{1}(x)} \cdot f_{1} (x) \\
& = (1 + 2^{n-1} x)(1 + 2^{n-2} x)……(1 + 2x)(1+a_{1,1}x) \\
& = (1 + 2^{n-1} x)(1 + 2^{n-2} x)……(1 + 2^1 x)(1+ 2^0x)
\end{align*}
よって、
f_{n} (x) = (1 + 2^{n-1} x)(1 + 2^{n-2} x)……(1 + 2^1 x)(1+ 2^0x)
\end{align*}
が得られました。以上から、
\frac{f_{n+1}(x)}{f_n(2x)} & = \frac{(1 + 2^{n} x)(1 + 2^{n-2} x)……(1 + 2^1 x)(1+ 2^0x)}{(1 + 2^{n-1} \cdot 2x)(1 + 2^{n-2} \cdot 2x)……(1 + 2^1 \cdot 2x)(1+ 2^0 \cdot 2x)} \\
& = \frac{(1 + 2^{n} x)(1 + 2^{n-2} x)……(1 + 2^1 x)(1+ 2^0x)}{(1 + 2^{n} x)(1 + 2^{n-2} x)……(1 + 2^2 x)(1+ 2^1x)} \\
& = 1 + 2^0 x \\
& = 1 + x
\end{align*}
となりますね。めでたしめでたし。
(3) 誘導をフル活用してゴリ押し
ここまで頑張って乗り越えられれば、あとは比較的簡単です。（とは言っても難しいですが）
(2) の式を使って頑張るのみです。
$$ a_{n+1, k+1} = 2^n a_{n, k} + a_{n, k+1} $$
から、すべきことは \(a_{n, k+1}\) を消去すること。
そこで、(2) 後半の結論である、
$$ f_{n+1} (x) = (1+x) f_n (2x) $$
について、係数比較をして漸化式を強引にもう一つ作ってみます。\(f_{n+1} (x)\) の \(x^{k+1}\) の係数が \(a_{n+1, k+1}\) であることに注意して、 \(x^{k+1}\) の係数を両辺で比較してやると、
f_{n+1} (x) = (1+x)(1 + a_{n, 1} 2x + a_{n, 2} (2x)^2 + …… + a_{n, n} (2x)^n)
\end{align*}
a_{n+1, k+1} = 2^{k+1} a_{n, k+1} + 2^k a_{n, k}
\end{align*}
が得られます。これより \(a_{n, k+1}\) を消去すれば、
a_{n+1, k+1} = 2^{k+1} (a_{n+1, k+1} – 2^n a_{n, k}) + 2^k a_{n, k}
\end{align*}
よって
\frac{a_{n+1, k+1}}{a_{n, k}} = \frac{2^k (2^{n+1} – 1)}{2^{k+1} – 1}
\end{align*}
となります。
難しくない？僕は試験場で解けないです絶対