https://spherical-harmonics.hateblo.jp/entry/Kyodai/2013/Rikei

2025.05.10記

[2] $N$ を2以上の自然数とし， $a_n$ $(n=1，2，\cdots)$ を次の性質(i)，(ii)をみたす数列とする．

(i) $a_1=2^N-3$ ．

(ii) $n=1，2，\cdots$ に対して，

$a_n$ が偶数のとき $a_{n+1}=\dfrac{a_n}{2}$ ， $a_n$ が奇数のとき $a_{n+1}=\dfrac{a_n-1}{2}$ ．

このときどのような自然数 $M$ に対しても $\displaystyle\sum_{n=1}^Ma_n \leqq 2^{N+1}-N-5$ が成り立つことを示せ．

本問のテーマ

右シフト演算

2025.05.22記
2進数表示で考えると，自然数 $a_n$ も末尾を除いたものが $a_{n+1}$ となり，全ての桁が取り除かれた場合，それ以降 $0$ が続く数列となる．この操作はプログラミングでは右シフト演算と呼ばれている．東大なんかは今後情報や統計と絡めた数学の問題を時々出題しそうなので，プログラミングで登場するビットシフトについて知っておくと良さげ．

右シフト演算については
2007年(平成19年)一橋大学後期-数学[2] - [別館]球面倶楽部零八式markIISR

左シフト演算はベルヌーイ写像の表現に用いられる：
パイこね変換 - 球面倶楽部零八式 mark II

さて，例えば $N=10$ のとき
$a_1=1111111101_{(2)}=2^{10}-1-2$ ，
$a_2=111111110_{(2)}=2^{9}-1-1$ ，
$a_3=11111111_{(2)}=2^{8}-1$ ，
$a_4=1111111_{(2)}=2^{7}-1$ ，
$a_5=111111_{(2)}=2^{6}-1$ ，
$a_6=11111_{(2)}=2^{5}-1$ ，
$a_7=1111_{(2)}=2^{4}-1$ ，
$a_8=111_{(2)}=2^{3}-1$ ，
$a_9=11_{(2)}=2^{2}-1$ ，
$a_{10}=1_{(2)}=2^{1}-1$ ，
$a_{11}=0_{(2)}$
となり，以降 $0$ が続く数列となる．よってどのような自然数 $M$ についても
$\displaystyle\sum_{n=1}^Ma_n \leqq \displaystyle\sum_{n=1}^{10} a_n$ $=(2^{11}-2)-10-3=2^{11}-15$
が成り立つ．

[解答]
$a_n$ が正の整数のとき， $a_{n+1}\leqq \dfrac{a_n}{2} \lt a_n$ からより小さい正の整数となるので $a_n$ はやがて $0$ となり，一旦 $0$ になると後は $0$ が続く数列となる．

$a_1=2^N-3$ は奇数だから
$a_2=2^{N-1}-2$ となり，これは $N=2$ のとき $0$ であり $N\geqq 3$ のとき正の偶数である．

(a) $N=2$ のとき：
$a_2=0$ だから帰納的に $a_n=0$ （ $n\geqq 2$ ）となりどのような自然数 $M$ に対しても $\displaystyle\sum_{n=1}^M a_n = 1 \leqq 2^{2+1}-2-5=1$ が成り立つ．

(b) $N\geqq 3$ のとき：
$a_2=2^{N-1}-2$ は正の偶数だから $a_3=2^{N-2}-1$ となる．これは奇数であるから $a_4=2^{N-3}-1$ となり，これは $N=3$ のとき $0$ ， $N\geqq 4$ のとき奇数である．

$N\geqq 4$ のとき， $a_4=2^{N-3}-1$ となり，これは奇数であるから $a_5=2^{N-4}-1$ となり，これは $N=4$ のとき $0$ ， $N\geqq 5$ のとき奇数である．

これを続けると帰納的に
$a_1=2^N-3$ ， $a_2=2^{N-1}-2$ ，
$a_n=2^{N+1-n}-1$ （ $n=3，…，N$ ），
$a_n=0$ （ $n=N+1，N+2，…$ ）
であることがわかる．よって $f(M)=\displaystyle\sum_{n=1}^M a_n$ とおくと
$f(1)\lt f(2)\lt\cdots\lt f(N)=f(N+1)=f(N+2)=\cdots$
であることがわかるので，
$\displaystyle\sum_{n=1}^M a_n$ $\leqq \displaystyle\sum_{n=1}^N a_n$
$=(2^N-3)+(2^{N-1}-2)+(2^{N-2}-1)+\cdots+(2^2-1)+(2-1)$
$=(2^N-1)-2+(2^{N-1}-1)-1+(2^{N-2}-1)+\cdots+(2^2-1)+(2^1-1)$
$=(2^N+2^{N-1}+\cdots+2^1-N)-3$
$=(2^{N+1}-2-N)-3$ $=2^{N+1}-N-5$
が成り立つ．