【東京大学2020年度前期入試数学(理系)第4問】数列と整式問題の融合

今回は数列の問題ですが、数列の問題と整式の問題が半々といった感じの問題です。

東京大学安田講堂
2016年12月24日、 Kakidai撮影、Wikipediaより

[問題] n, k を 1 ≦ k ≦ n を満たす整数とする。n 個の 整数
　　　　　　　2^m　　(m = 0, 1, 2, … , n-1)
から異なる k 個を選んでそれらの積をとる。k 個の整数の選び方すべてに対しこのように積をとることにより得られる nCk 個の和を a(n,k) とおく。例えば、
　　a(4,3) = 2^0・2^1・2^2 + 2^0・2^1・2^3 + 2^0・2^2・2^3 + 2^1・2^2・2^3 = 120
である。
(1) 2 以上の整数 n に対し，a(n,2) を求めよ。
(2) 1 以上の整数 n に対し，x についての整式
　　　　　fn(x) = 1 + a(n,1) x + a(n,2) x^2 + …… + a(n,n) x^n
を考える。fn+1(x)/fn(x) と fn+1(x)/fn(2x) を x についての整式として表せ。
(3) a(n+1,k+1)/a(n,k) を n, k で表せ。
(注) a(n,k) は原文では a に添え字の n,k です。また、fn+1(x) も f に添え字の n+1 のあと (x) となります。

テキストで書くと式が分かりにくいかもしれませんが、そこは心の眼で見てください。笑

この問題は (1) と (3) の 2つの主題があって、(2) が (3) の誘導問題です。ですので、(1) が分からなくても (2) 以降には何の影響もありません。

ですが、(1) が分からない時点でこの問題を捨てる人もいるかもしれません。そういう早まったことをしてはいけません。

(1) は世間では (2^0 + 2^1 + … + 2^{n-1})^2 から求めていますが、同じことをしても仕方がないので、ここでは直接的に求めていきたいと思います。

それでは解答。a(n,2) を b(n) とでもおいておきます。(n,2) の 2 が邪魔なので置き換えただけです。それ以上の意味はありません。

定義から n ≧ 2 のときに b(n+1) = b(n) + 2^n × (2^0 + 2^1 + … + 2^{n-1}) = b(n) + 2^n (2^n -1) = b(n) + 2^{2n} - 2^n となりますが、これを変形すると

b(n+1) - 2^{2(n+1)}/3  + 2^{n+1} = b(n) - 2^{2n}/3 + 2^n

となるので、n ≧ 3 のとき

b(n) -2^{2n}/3 + 2^n = b(2) - 16/3 + 4 = 2/3 

が得られます(この式は n = 2 のときにも成立します)。ここで、b(2) = a(2, 2) = 2^0 × 2^1 = 2 です。以上のことから、

a(n,2) = b(n) = 2^{2n}/3 - 2^n + 2/3

が答えとなります。

(2) は gn(x) = (1 + (2^0) x)(1 + (2^1) x)…(1 + (2^{n-1}) x) とおいて展開して、fn(x) と比較することで fn(x) = gn(x) が得られます。それだけです。

(これ、どこまで説明が必要なんでしょうか？)

すると、fn+1(x) = (1 + (2^0) x)(1 + (2^1) x)…(1 + (2^{n-1}) x)(1 + (2^n) x) かつ fn(2x) = (1 + (2^1) x)…(1 + (2^{n-1}) x)(1 + (2^n) x) から

fn+1(x)/fn(x) = 1 + (2^n) x かつ fn+1(x)/fn(2x) = 1 + (2^0) x = 1 + x

が求まります。

(3) は (2) の2つの式を使って係数を比べるだけです。

fn+1(x) = (1 + (2^n) x) fn(x) = (1 + x) fn(2x)

の x^{k+1} の係数を比較することで、

a(n+1,k+1) = a(n,k+1) + 2^n × a(n,k) = 2^{k+1} × a(n,k+1) + 2^k × a(n,k)

が得られます。ただし、n > k が条件になりますので注意してください。

この式から a(n,k+1) を a(n,k) で表すと、a(n,k+1) = {(2^n  - 2^k) / (2^{k+1} - 1)} × a(n,k) となります。よって、

a(n+1,k+1) = {(2^n  - 2^k) / (2^{k+1} - 1)} × a(n,k) + 2^n × a(n,k) = { 2^k × (2^{n+1} - 1) }/(2^{k+1} - 1) } × a(n,k)

より

a(n+1,k+1)/a(n,k) = 2^k × (2^{n+1} - 1)/(2^{k+1} - 1) 

が求まります。この式の右辺は n = k のときに 2^n となり、このときにも正しいことが簡単に確認できました。[解答終]

この問題の肝は何かというと、(2) と (3) については fn(x) の因数分解ができるかです。逆に言えば、それさえ分かればあとは一本道です。

(1) については、予備校の解答では (2^0 + 2^1 + … + 2^{n-1})^2 の展開を思い浮かべられるかを肝としています。

(2^0 + 2^1 + … + 2^{n-1})^2 = (4^0 + 4^1 + … + 4^{n-1}) + 2 × a(n,2)

に 2^0 + 2^1 + … + 2^{n-1} = 2^n - 1 かつ 4^0 + 4^1 + … + 4^{n-1} = (4^n - 1)/3  を代入して、

4^n - 2^{n+1} + 1 = (4^n/3) - (1/3) + 2a(n,2) 

これを整理して a(n,2) = (1/3)×4^n - 2^n + (2/3) が得られます。

確かにこの問題に対しては簡単で効率が良く実践的である一方、ここで提示した方法は素直な方法で、より汎用性が高いです。

まず、ここで提示した方法だと a(n+1, k) = a(n, k) + 2^n × a(n, k-1) として、k = 2, 3,... と順に求めていくことが可能です。漸化式を解くのも難しくありません。

(ちなみに、この式の k に k + 1 を代入した式が (3) で求められていますが、実は (1) の漸化式の一般化としてノーヒントで導出できます。)

式変形についても、b(n+1) = b(n) + D × c^n    (c ≠ 1) という形の漸化式を解くためには、まず b(n+1) + C × c^{n+1} = b(n) + C × c^n とおいて、ここから変形した式 b(n+1) = b(n) + (1 - c) × C × c^n と最初の漸化式を比較することで、C = D/(1-c) と求まります。

C が求まったら、b(n) + C × c^n = b(n-1) + C × c^{n-1} = … と初項まで落としてあげれば漸化式が解けます。

ちなみに、c = 1 のときには b(n+1) = b(n) + D となるので、これは等差数列です。

この方法は線形の二項間漸化式であれば使えるので、覚えておくといいでしょう。

ここまで見てきたように、今回提示した (1) を解く方法は汎用性が高く、使い勝手が良いので覚えておく価値が高いと考えています。

予備校などで提示した (2^0 + 2^1 + … + 2^{n-1})^2 を展開する方法も確かに使われる場所がそこそこにあるので知っておく価値はあります。悪い方法ではありません。むしろスマートな方法です。

あくまで優先順位としてどちらをまず先に知っておくべきかという話で、解説で示した二項間漸化式の解き方は私に言わせれば基本中の基本なので、ぜひ知っておいてください。