OMC145(F)

公式解説における $S_n$ を求める過程です.

$n-1$ を $2$ 進法表示すると，操作は以下のように表せる.

• $1$ の位が $1$ のとき，その $1$ を取り除く.
• $1$ の位が $0$ のとき，これを $1$ に変える.

$a_n$ は操作で値が $0$ になるまでの回数であり，これは $n-1$ を $2$ 進法表示したときの $$(各位に現れる0の個数)×2+(各位に現れる1の個数)$$ に等しい (ただし，最高位は $0$ ではないものとする. ). したがって，$2^{k-1}+1\leq n\leq 2^{k}$ における $a_n$ の期待値は，$1+\dfrac{3}{2}(k-1)=\dfrac{3}{2}k-\dfrac{1}{2}$ であるから，$S_n=2^{n-2}(3n-1)$ がわかる.