京都大学 2013年 理系 第2問 解説

方針・初手

• 数列 $a_n$ の遷移ルールは「偶数なら $2$ で割る」「奇数なら $1$ を引いて $2$ で割る」という操作で、2 進数表示において「最下位ビットを削る（右シフトする）」操作に相当する。
• 具体的に $a_1, a_2, a_3, \ldots$ を計算して一般項を推測し、数学的帰納法で確定させた上で総和を計算する。
• $a_n = 2a_{n+1} + (\text{余り})$ と変形し辺々を足し合わせるエレガントな別解もある。

解法1（一般項を求めて総和）

$N=2$ の場合

$a_1 = 1$（奇数）、$a_2 = 0$、以降 $a_n = 0$。総和 $= 1$、右辺 $= 2^3-2-5=1$ なので $1 \leq 1$ ✓

$N \geq 3$ の場合

$a_1 = 2^N - 3$（奇数）、$a_2 = 2^{N-1}-2$（偶数）、$a_3 = 2^{N-2}-1$。

主張： $3 \leq k \leq N$ に対して $a_k = 2^{N-k+1} - 1$。

帰納法：

• $k=3$：$a_3 = 2^{N-2}-1$ ✓
• $a_m = 2^{N-m+1}-1$（$N-m+1 \geq 2$ なので奇数）が成り立つとき：

$$ a_{m+1} = \frac{a_m - 1}{2} = \frac{2^{N-m+1}-2}{2} = 2^{N-m} - 1 = 2^{N-(m+1)+1} - 1 \quad \checkmark $$

特に $k=N$ のとき $a_N = 1$（奇数）、$a_{N+1} = 0$、以降 $a_n = 0$。

$a_n \geq 0$ より和は単調非減少なので、最大値は $M \geq N$ のときの値。

$$ S = (2^N - 3) + (2^{N-1} - 2) + \sum_{k=3}^{N}(2^{N-k+1} - 1) $$

$j = N-k+1$ と置換すると $\displaystyle\sum_{k=3}^{N}(2^{N-k+1}-1) = \sum_{j=1}^{N-2}(2^j-1) = (2^{N-1}-2)-(N-2) = 2^{N-1}-N$

$$ S = (2^N-3) + (2^{N-1}-2) + (2^{N-1}-N) = 2^{N+1} - N - 5 $$

よって任意の自然数 $M$ に対して $\displaystyle\sum_{n=1}^{M} a_n \leq 2^{N+1} - N - 5$。$\blacksquare$

解法2（漸化式の総和処理）

$a_n$ を $2$ で割ったときの余りを $r_n$（$\in\{0,1\}$）とおくと、操作の定義より

$$ a_n = 2a_{n+1} + r_n $$

$n=1$ から $M$ まで辺々を足し合わせると、

$$ \sum_{n=1}^{M} a_n = 2\sum_{n=2}^{M+1} a_n + \sum_{n=1}^{M} r_n = 2\!\left(\sum_{n=1}^{M} a_n - a_1 + a_{M+1}\right) + \sum_{n=1}^{M} r_n $$

整理して、

$$ \sum_{n=1}^{M} a_n = 2a_1 - 2a_{M+1} - \sum_{n=1}^{M} r_n = 2^{N+1} - 6 - 2a_{M+1} - \sum_{n=1}^{M} r_n $$

解法1の奇偶の確認より $r_1=1$、$r_2=0$、$r_3=\cdots=r_N=1$、$n \geq N+1$ では $r_n=0$。

$M \geq N$ のとき $a_{M+1} = 0$、$\displaystyle\sum_{n=1}^{M} r_n = N-1$（最大値）であるから、

$$ \sum_{n=1}^{M} a_n = 2^{N+1} - 6 - (N-1) = 2^{N+1} - N - 5 $$

$a_n \geq 0$ より和は単調非減少なので、任意の $M$ に対して $\displaystyle\sum_{n=1}^{M} a_n \leq 2^{N+1} - N - 5$。$\blacksquare$

解説

一見見慣れない漸化式だが、具体的に書き下すと規則性が見えてくる。「困ったら実験する」という数列問題の鉄則が活きる問題である。

解法1が確実だが、解法2の $a_n = 2a_{n+1} + r_n$ と変形して「和の形を丸ごと作り出す」テクニックは、整数問題や 2 進数と絡めた数列問題で非常に強力な武器になる。

答え

略（解法1の証明を参照）