Evolton

京都大学 2013年度 前期日程 第2次学力試験理系数学 第2問

N を2以上の自然数とし、数列 an (n=1,2,…) が次の条件を満たすとする。

(i) a1=2N−3.

(ii) n=1,2,… に対して、an+1={an2(an が偶数のとき),an−12(an が奇数のとき).このとき、どのような自然数 M に対しても∑n=1Man≦2N+1−N−5が成り立つことを示せ。

難易度5/ 10計算量4/ 10目安18分

数列、整数 帰納的定義の利用、和の計算、数え上げ

方針

漸化式は an+1 が an を2で割った商であることを表す。2進表示では右端の1桁を消す操作なので、初項 2N−3 に立っている各ビットが、消えるまで部分和へ寄与する量を足せばよい。数列はやがて0になり、全項が非負なので、任意の有限部分和は0になるまでの総和以下である。

解答

条件(ii)は、an を2で割った商が an+1 であることを表す。したがって2進表示では、各段階で右端の1桁を消す。

初項はa1=2N−3=1+∑j=2N−12j.(1)N=2 のとき、右辺の和は空和である。(1)より、2進表示では 20 の位と 22,…,2N−1 の位が1であり、21 の位だけが0である。

最初に 2j の位にある1は、右へ1桁ずつ移り、消えるまでに全項の和へ2j+2j−1+⋯+2+1=2j+1−1(2)だけ寄与する。したがって、数列が0になるまでの総和は(21−1)+∑j=2N−1(2j+1−1)=1+(23+24+⋯+2N)−(N−2)=1+(2N+1−8)−(N−2)=2N+1−N−5.(3)すべての an は0以上であり、十分先では0になる。よって、どの自然数 M に対しても、M までの部分和は(3)の総和を超えない。したがって∑n=1Man≦2N+1−N−5が成り立つ。

別解

解法2(各項を明示して和を求める方法)

方針

最初の2項を計算した後、an=2N−n+1−1 という形が続くことを漸化式から確認する。この形の項は奇数なので、次の項は (an−1)/2 となって同じ形が保たれる。0になるまでの全項を等比数列の和として足し、非負項の部分和をその総和で上から押さえる。

解答

まずa1=2N−3は奇数なのでa2=a1−12=2N−1−2.N=2 なら a2=0 であり、∑n=1Man≦a1=1=23−2−5となる。以下 N≧3 とする。

a2 は偶数だからa3=a22=2N−2−1.さらにan=2N−n+1−1(3≦n≦N)(1)が成り立つとき、n<N なら an は奇数なのでan+1=an−12=2N−n−1.よって(1)は帰納的に成り立つ。特にaN=1,aN+1=0であり、それ以後も0である。

したがって全項の和は∑n=1∞an=(2N−3)+(2N−1−2)+∑n=3N(2N−n+1−1)=(2N−3)+(2N−1−2)+(2N−2+2N−3+⋯+2)−(N−2)=2N+1−N−5.各項は非負なので、任意の自然数 M に対して∑n=1Man≦∑n=1∞an=2N+1−N−5である。

総評

難度5、目安時間18分。漸化式は偶奇を別々に追うより、「2で割った商」あるいは「2進表示の右端を1桁消す操作」と読むのが本質である。解法1は各ビットの寄与を一度に数え、解法2は a3,…,aN を明示して総和を計算する。どちらでも N=2 の端の場合と、数列が0になった後も項が0のままであることを確認し、任意の M の部分和へ結びつける必要がある。

Evolton Pro

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

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

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