Evolton

東京大学 2020年度 前期日程 第2次学力試験文系数学 第4問

n,kを,1≦k≦nを満たす整数とする。n個の整数2m(m=0, 1, 2, ⋯⋯ , n−1)から異なるk個を選んでそれらの積をとる。
k個の整数の選び方すべてに対しこのように積をとることにより得られる
nCk個の整数の和をan,kとおく。例えば,a4,3=20⋅21⋅22+20⋅21⋅23+20⋅22⋅23+21⋅22⋅23=120である。

(1) 2以上の整数nに対し,an,2を求めよ。

(2) 1以上の整数nに対し,xについての整式fn(x)=1+an,1x+an,2x2+⋯⋯+an,nxnを考える。
fn+1(x)fn(x)と
fn+1(x)fn(2x)を
xについての整式として表せ。

(3) an+1,k+1an,kをn,kで表せ。

難易度6/ 10計算量6/ 10目安25分

数列、場合の数、数と式 数え上げ、式変形、誘導利用、計算整理

方針

an,k を整式 fn(x) の係数として捉える。(1)は平方和を引いて求め、(2)は fn を積に分解する。(3)は fn+1(x) を (1+2nx)fn(x) と (1+x)fn(2x) の2通りに表し、係数比較で不要な比を消去する。

解答

(1) an,2=∑0≦i<j≦n−12i+j.全体の和の平方から同じ項どうしの積を除くとan,2=12{(1+2+⋯+2n−1)2−(1+22+⋯+22n−2)}.等比数列の和を代入してan,2=12{(2n−1)2−4n−13}=4n−3⋅2n+23.(2)

各因子から定数項または 2mx を選んで展開すると、xk の係数がちょうど an,k になる。よってfn(x)=(1+x)(1+2x)⋯(1+2n−1x).したがってfn+1(x)=(1+2nx)fn(x)およびfn+1(x)=(1+x)fn(2x)であるから、fn+1(x)fn(x)=1+2nx,fn+1(x)fn(2x)=1+x.(3)

第1の恒等式で xk+1 の係数を比較するとan+1,k+1=an,k+1+2nan,k.第2の恒等式からはan+1,k+1=2k+1an,k+1+2kan,k.両式を引いて(2n−2k)an,k=(2k+1−1)an,k+1,したがってan,k+1an,k=2n−2k2k+1−1.これを最初の式へ戻せばan+1,k+1an,k=2n+2n−2k2k+1−1=2k(2n+1−1)2k+1−1.k=n の場合も右辺は 2n となり、式はそのまま成り立つ。

別解

解法2(明示公式を帰納的に作る方法)

方針

(1) は大きい方の指数を固定した二重和で計算する。(2)の積表示から「2n−1 を選ぶか否か」で漸化式を作り、an,k の明示公式を数学的帰納法で確かめる。(3)は明示公式の比をとり、連続する因子を消去する。

解答

(1)

大きい方の指数を j とするとan,2=∑j=1n−12j(1+2+⋯+2j−1)=∑j=1n−1(4j−2j)=4n−43−(2n−2)=4n−3⋅2n+23.(2)

選んだ指数を係数として記録するためfn(x)=(1+x)(1+2x)⋯(1+2n−1x).よって直ちにfn+1(x)fn(x)=1+2nx,fn+1(x)fn(2x)=1+x.(3)

k 個を選ぶとき 2n−1 を選ばない場合と選ぶ場合に分けるとan,k=an−1,k+2n−1an−1,k−1.この漸化式から数学的帰納法によりan,k=2k(k−1)/2(2n−1)(2n−1−1)⋯(2n−k+1−1)(2k−1)(2k−1−1)⋯(2−1)を得る。

実際、右辺を Bn,k とおくとBn−1,kBn,k=2n−k−12n−1,また2n−1Bn−1,k−1Bn,k=2n−k(2k−1)2n−1.この2つの比の和は1なので、Bn,k は上の漸化式を満たす。初期値も一致するから明示公式が従う。

したがって、連続する因子を消去すればan+1,k+1an,k=2k2n+1−12k+1−1.

総評

難度6、計算量6。想定時間は25分程度。整式 fn(x) を積で表すことが全体の中心である。(3)では2つの恒等式から同じ係数を比較し、an,k+1/an,k を一度求めてから目的の比へ戻すと見通しがよい。明示公式を使う方法では、漸化式との整合を比の和が1になる形で確認すると計算が短い。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の数列の問題で問題集を作る

出典: 東京大学 2020年度 前期日程 第2次学力試験 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。