2.2.28

簡単に書くために$$[x] := x \bmod 2$$と定義する。 パスカルの三角形と二項係数の関係から、 $$g(n) = [\binom{n}{0}] + [\binom{n}{1}] + \cdots + [\binom{n}{n}]$$である。 これを簡単な式で表せるようにするのが目的である。

パスカルの三角形を偶数を0、奇数を1で表すと以下のようになる。

               1
              1 1
             1 0 1
            1 1 1 1
           1 0 0 0 1
          1 1 0 0 1 1
         1 0 1 0 1 0 1
        1 1 1 1 1 1 1 1
       1 0 0 0 0 0 0 0 1
      1 1 0 0 0 0 0 0 1 1
     1 0 1 0 0 0 0 0 1 0 1
    1 1 1 1 0 0 0 0 1 1 1 1
   1 0 0 0 1 0 0 0 1 0 0 0 1
  1 1 0 0 1 1 0 0 1 1 0 0 1 1
 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

よって$$g(n)$$は

となる。$$g(n)$$が2の累乗の形になっているので$$n$$を2進法で表し、また$$g(n)$$を2を底とする対数と比較してみると次のようになる。

これから$$g(n) = 2^{"\text{nの立っているビットの数}"}$$と予想できる。

これを$$n$$に関する帰納法で示す。 証明しやすいように$$g(n)$$を漸化式の形で書き換えると、 $$\begin{array}{rcl} g(0) &=& 1\\ g(2n) &=& g(n), (n>0)\\ g(2n+1) &=& 2g(n), (n \geq 0) \end{array}$$ となりこれを示せば良い。ただし便宜上$$g(0) = 1$$とした。

$$\binom{2n}{k}$$が扱いづらいので、まず以下の補題を示す。 $$\binom{2n}{k} = \sum_{\begin{array}{c}i+j=k\\0\leq i,j\end{array}}\binom{n}{i}\binom{n}{j}$$ 二項定理より$$\binom{2n}{k}$$は$$(x+1)^{2n}$$の$$x^k$$の係数である。 一方$$(x+1)^{2n} = (x+1)^n(x+1)^n = (\sum_{i=0}^n\binom{n}{i}x^i)(\sum_{j=0}^n\binom{n}{j}x^j)$$ であるから$$x^k$$の係数は$$\sum_{\begin{array}{c}i+j=k\\0\leq i,j\leq n\end{array}}\binom{n}{i}\binom{n}{j}$$である。 $$n < i$$のとき$$\binom{n}{i} = 0$$なので$$i,j \leq n$$の制約をなくしてもよいのでこれは $$\sum_{\begin{array}{c}i+j=k\\0\leq i,j \end{array}}\binom{n}{i}\binom{n}{j}$$である。 これらの$$x^k$$の係数が一致するので補題が成り立つ。

まず漸化式$$g(2n) = g(n)$$が成り立つことを示す。 補題を使えば、 $$\left[\binom{2n}{k}\right] = \left[\binom{n}{0}\binom{n}{k} + \binom{n}{1}\binom{n}{k-1} + \cdots + \binom{n}{k}\binom{n}{0}\right]$$ なので$$k$$が奇数のとき$$k=2l+1$$として $$\left[\binom{2n}{k}\right] = \left[2\binom{n}{0}\binom{n}{k} + 2\binom{n}{1}\binom{n}{k-1} + \cdots + 2\binom{n}{l}\binom{n}{l+1}\right] = 0$$ と打ち消すようにして0となる。 一方$$k$$が偶数のときは$$k=2l$$として $$\begin{array}{rcl} \left[\binom{2n}{k}\right] &=& \left[2\binom{n}{0}\binom{n}{k} + 2\binom{n}{1}\binom{n}{k-1} + \cdots + 2\binom{n}{l-1}\binom{n}{l+1} + \binom{n}{l}\binom{n}{l}\right]\\ &=& \left[\binom{n}{l}\binom{n}{l}\right] = \left[\binom{n}{l}\right] \end{array}$$ となる。

結局$$g(2n)$$は偶数の部分しか残らないので $$\begin{array}{rcl} g(2n) &=& \left[\binom{2n}{0}\right] + \left[\binom{2n}{1}\right] + \cdots + \left[\binom{2n}{2n}\right]\\ &=& \left[\binom{n}{0}\right] + \left[\binom{n}{1}\right] + \cdots + \left[\binom{n}{n}\right]\\ &=& g(n) \end{array}$$ となり漸化式が成り立つ。

次に$$g(2n+1) = 2g(n)$$を示す。 $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$を使えば $$g(2n+1) = \left[\binom{2n}{0}\right] + \left[\binom{2n}{0} + \binom{2n}{1}\right] + \cdots + \left[\binom{2n}{2n-1} + \binom{2n}{2n}\right] + \left[\binom{2n}{2n}\right]$$ となる。 $$\left[\binom{2n}{i}\right]$$は$$i$$が奇数のとき0であったから $$\left[\binom{2n}{i}\right], \left[\binom{2n}{i+1}\right]$$のどちらかは0になる。従って $$\left[\binom{2n}{i} + \binom{2n}{i+1}\right] = \left[\binom{2n}{i}\right] + \left[\binom{2n}{i+1}\right]$$ とかける。故に $$\begin{array}{rcl} g(2n+1) &=& 2\left(\left[\binom{2n}{0}\right] + \left[\binom{2n}{1}\right] + \cdots + \left[\binom{2n}{2n}\right]\right)\\ &=& 2g(2n) = 2g(n) \end{array}$$ が成り立つ。