解説

方針・初手

$f(m)=[m-\log_2(m+1)]$ は、整数から実数を引いたものの床である。したがって、まず

$$ [n-\alpha]= \begin{cases} n-\alpha & (\alpha\in \mathbb{Z})\\ n-[\alpha]-1 & (\alpha\notin \mathbb{Z}) \end{cases} \qquad (n\in \mathbb{Z}) $$

という基本事実を使うのが自然である。

あとは $\log_2(m+1)$ や $\log_2(m+2)$ が整数かどうか、またその整数部分がどうなるかを調べればよい。

解法1

まず、整数 $n$ と実数 $\alpha$ に対して、上の公式が成り立つことを確認しておく。

$\alpha\in \mathbb{Z}$ のときは $n-\alpha$ 自身が整数であるから

$$ [n-\alpha]=n-\alpha $$

である。

また $\alpha\notin \mathbb{Z}$ のとき、$[\alpha]\le \alpha<[\alpha]+1$ より

$$ n-[\alpha]-1<n-\alpha\le n-[\alpha] $$

となる。ここで $n-[\alpha]$ は整数であるから

$$ [n-\alpha]=n-[\alpha]-1 $$

である。

以上を用いて、それぞれ示す。

（1） $m+1=2^s$ となる整数 $s$ がある場合

このとき

$$ \log_2(m+1)=s $$

であり、これは整数である。したがって

$$ f(m)=[m-\log_2(m+1)]=[m-s]=m-s $$

となる。

次に、$m+1=2^s$ であるから

$$ m+2=2^s+1 $$

であり、

$$ 2^s<m+2<2^{s+1} $$

が成り立つ。よって

$$ s<\log_2(m+2)<s+1 $$

となり、$\log_2(m+2)$ は整数ではなく、その整数部分は $s$ である。したがって

$$ f(m+1)=[m+1-\log_2(m+2)] $$

は、先ほどの公式より

$$ f(m+1)=m+1-s-1=m-s $$

となる。

ゆえに

$$ f(m+1)=f(m) $$

である。

（2） $m+1=2^s$ となる整数 $s$ がない場合

このとき $\log_2(m+1)$ は整数ではない。$s=[\log_2(m+1)]$ とおくと

$$ s<\log_2(m+1)<s+1 $$

であるから

$$ 2^s<m+1<2^{s+1} $$

が成り立つ。

これに $1$ を加えると

$$ 2^s+1<m+2\le 2^{s+1} $$

となるので

$$ s<\log_2(m+2)\le s+1 $$

を得る。したがって $\log_2(m+2)$ の整数部分も $s$ である。実際、

• $m+2\neq 2^{s+1}$ なら $\log_2(m+2)$ は整数でなく $[\log_2(m+2)]=s$
• $m+2=2^{s+1}$ なら $\log_2(m+2)=s+1$

である。

まず、$\log_2(m+1)$ は整数でないから

$$ f(m)=[m-\log_2(m+1)]=m-s-1 $$

である。

次に $f(m+1)$ を求める。

**(i)**

$\log_2(m+2)$ が整数でない場合

このとき $[\log_2(m+2)]=s$ であるから

$$ f(m+1)=[m+1-\log_2(m+2)]=m+1-s-1=m-s $$

となる。

**(ii)**

$\log_2(m+2)$ が整数の場合

このとき $\log_2(m+2)=s+1$ であるから

$$ f(m+1)=[m+1-(s+1)]=m-s $$

となる。

いずれの場合も

$$ f(m+1)=m-s $$

であり、先ほどの $f(m)=m-s-1$ と合わせて

$$ f(m+1)=f(m)+1 $$

が成り立つ。

解説

要点は、$f(m)$ を直接いじるのではなく、$\log_2(m+1)$ が整数か非整数かで場合分けすることである。

特に

$$ [n-\alpha] $$

の形では、$\alpha$ が整数かどうかで床の値が $1$ だけずれる。この問題は、そのずれがちょうど

• $m+1$ が $2$ のべきのときは打ち消されて $f(m+1)=f(m)$
• そうでないときはそのまま残って $f(m+1)=f(m)+1$

となることを見抜けるかが核心である。

答え

**(1)**

$m+1=2^s$ となる整数 $s$ があるとき、

$$ f(m+1)=f(m) $$

である。

**(2)**

$m+1=2^s$ となる整数 $s$ がないとき、

$$ f(m+1)=f(m)+1 $$

である。