https://spherical-harmonics.hateblo.jp/entry/Hitotsubashi/2007/Kouki

2024.09.15記

[2] 数列 $\{a_n\}$ は
$a_1=1$ ， $a_{2n}=2a_n-1$ ， $a_{2n+1}=2a_n+1$
をみたす．

(1) $n=2^m$ のとき， $a_n$ を求めよ．

(2) $n=2^m+r$ （ $r=1，2，\cdots，2^m-1$ ）のとき， $a_n$ を求めよ．

本問のテーマ

2進数の桁数
右シフト演算

2024.09.15記
結果を予測するために実験してみることが大切で、
$a_1=1$ ，
$a_2=2a_1-1=1$ ， $a_3=2a_1+1=3$ ，
$a_4=2a_2-1=1$ ， $a_5=2a_2+1=3$ ， $a_6=2a_3-1=5$ ， $a_7=2a_3+1=7$ ，
$a_8=2a_4-1=1$ ，…
から $a_n=2r+1$ と予測でき，予測できた後は
$n=2^k，\cdots，2^{k+1}-1$ ( $2^k$ 個の $n$ での成立を仮定)
での成立から
$n=2^{k+1}，\cdots，2^{k+2}-1$ ( $2^{k+1}$ 個の $n$ での成立を導く)
ｎで成立することを示す．

[解答]
(1) $a_1-1=0$ ， $a_{2n}-1=2(a_n-1)$ より帰納的に $a_{2^m}-1=0$ となり， $a_{2^m}=1$ となる．

(2) （ $m=0$ のときは $r=0$ となるので， $m=1，2，\cdots$ とする）

$a_{2^m+r}=2r+1$ （ $r=0，1，2，\cdots，2^m-1$ ）を示す．

(i) $m=1$ のとき， $a_{2^1+0}=a_2=2a_1-1=1$ ， $a_{2^1+1}=a_3=2a_1+1=3$ より成立．

(ii) $m=k$ のときの成立を仮定すると
$a_{2^k+r}=2r+1$ （ $r=0，1，2，\cdots，2^k-1$ ）
である．このとき

(a) $r=2u$ （ $u=0，1，2，\cdots，2^{k-1}-1$ ）のとき
$a_{2^{k+1}+2u}=2a_{2^{k}+u}-1=2(2u+1)-1=2r+1$ ，

(b) $r=2u+1$ （ $u=0，1，2，\cdots，2^{k-1}-1$ ）のとき
$a_{2^{k+1}+2u+1}=2a_{2^k+u}+1=2(2u+1)+1=2r+1$

であるから，
$a_{2^{k+1}+r}=2r+1$ （ $r=0，1，2，\cdots，2^{k+1}-1$ ）
でも成立する．よって題意は成立する．

（2024.09.21追記－ここから－）

与えられた数列は $a_1=1$ ， $a_{2n}=2a_n-1$ ， $a_{2n+1}=2a_n+1$ をみたすことから奇数列であることがわかる．そこで，奇数列を偶数列にして2で割ることを考えて
$b_n=\dfrac{a_n-1}{2}$ とおくと
$b_1=0$ ， $b_{2n}=2b_n$ ， $b_{2n+1}=2b_n+1$
と変形できる．ここで $b_1=1$ ならば $b_n=n$ となるので $b_1=1$ と $b_1=0$ の違いがどのように伝播していくかを考える（ $b_1=1$ のときの $b_n$ と $n$ の違いを見る）．すると

$b_1=0$ ，
$b_2=0$ ， $b_3=1=3-2$ ，
$b_4=0$ ， $b_5=1=5-4$ ， $b_6=2=6-4$ ， $b_7=3=7-4$ ，
$b_8=0$ ， $b_8=1=9-1$ ， $b_{10}=2=10-8$ ，…
と区切ることにより， $b_n$ は $n$ から先頭の数を引いたものとなる．この状況を表現するには2進数が効果的である．

[うまい解答]
$b_n=\dfrac{a_n-1}{2}$ （ $n=1，2，\cdots$ ）とおくと
$b_1=0$ ， $b_{2n}=2b_n$ ， $b_{2n+1}=2b_n+1$
と変形できる．ここで $b_1=1$ ならば $b_n=n$ となるので

2進数で考えると「2倍する」とは末尾に $0$ を追加することで，「2倍して1を足す」とは末尾に $1$ を追加することであるから，漸化式 $b_{2n}=2b_n$ ， $b_{2n+1}=2b_n+1$ は2進数で考えると，

$b_{(n\mbox{の末尾に0を追加})}\quad\quad\quad$ $=(b_nの末尾に0を追加)$ ，
$b_{(n\mbox{の末尾に1を追加})}\quad\quad\quad$ $=(b_nの末尾に1を追加)$

という漸化式となる．つまり $b_1=0$ だから $n$ と $b_n$ は先頭が 1 か 0 で異なるものの，それ以降に末尾に追加される0，１は同じであることがわかる．

よって $2^m\leqq n\lt 2^{m}$ （ $m$ は0以上の整数）のとき， $b_n=n-2^m$ となる．

(1) $b_n=0$ より $a_n=1$ となる．

(2) $b_n=n-2^m=r$ より $a_n=2r+1$ となる．

（ここまで2024.09.21追記）

次に，変わった置き換えをしてみよう．次の [大人の解答] に登場する
$n\mapsto \left[\dfrac{n}{2}\right]$
は右シフト演算（単に2進数で最後の桁を削除する演算）であり，例えば $13=1101\mapsto 7=110$ となる．

[大人の解答]
$L_n=\log_2(2n-a_n+1)$ （ $n=1，2，\cdots$ ）とおくと
$a_n=2n-2^{L_n}+1$
であるから，
$2-2^{L_1}+1=1$ ， $4n-2^{L_{2n}}+1=4n-2^{L_n+1}+2-1$ ， $4n+2-2^{L_{2n+1}}+1=4n-2^{L_n+1}+2+1$ ，
つまり
$L_1=1$ ， $L_{2n}=L_{2n+1}=L_n+1$
が成立する．これはガウス記号を用いて
$L_1=1$ ， $L_n=L_{\left[\frac{n}{2}\right]}+1$
と表すことができるので，

$L_n$ は自然数 $n$ を2進法で表したときの桁数

である．

(1)(2) $n=2^m+r$ （ $r=0，1，2，\cdots，2^m-1$ ）のとき， $n$ は $m+1$ 桁の2進数であるから $L_n=m+1$ である．よって
$m+1=\log_2(2^{m+1}+2r-a_n+1)$
となり， $a_n=2r+1$ となる．

突拍子もない置き換えだったので，それに至る過程も含めて答案にしてみよう．

まず，
$a_{2n}=2a_n-1$ ， $a_{2n+1}=2a_n+1$
は，奇数列を偶数列にして2で割ることを考えて
$b_n=\dfrac{a_n-1}{2}$ とおくと
$b_1=0$ ， $b_{2n}=2b_n$ ， $b_{2n+1}=2b_n+1$
と変形できる．ここで漸化式の添字の規則性から，初項は合わないが $b_n=n$ は漸化式を満たすことから

$c_n=n-b_n$ （初項をみて， $b_n-n$ ではなく $n-b_n$ とおく）

とおけば，漸化式で $n$ に依存する部分が逓減されて
$c_1=1$ ， $c_{2n}=c_{2n+1}=2c_n$
と漸化式が単純になる．このとき，実験してみると
$c_1=1$ ，
$c_2=c_3=2$ ，
$c_4=c_5=c_6=c_7=4$ ，…
$c_{2^m}=\cdots=c_{2^{m+1}-1}=2^m$ ，…
となり， $c_n=r$ であることが見え， $a_n=2r+1$ となることが見えるだろう（だから普通は帰納法で示すことになる）．

[うまい解答]
$b_n=\dfrac{a_n-1}{2}$ （ $n=1，2，\cdots$ ）とおくと
$b_1=0$ ， $b_{2n}=2b_n$ ， $b_{2n+1}=2b_n+1$
をみたす．さらに $c_n=n-b_n$ とおくと
$c_1=1$ ， $c_{2n}=c_{2n+1}=2c_n$
が成立する．これはガウス記号を用いて
$c_1=1$ ， $c_n=2c_{\left[\frac{n}{2}\right]}$
と表すことができるので，
$L_n=\log_2 c_n +1$
とおくと
$L_1=1$ ， $L_n=L_{\left[\frac{n}{2}\right]}+1$
と表すことができ，よって

$L_n$ は自然数 $n$ を2進法で表したときの桁数

である（以下略）．