横方向の和の和

昨日のブログではさぼったnusum (2^r-1) から nusum 2^rを計算してみた.

前回のような表を書くと

n	nusum	νn	es
2r-1	nusum 2r-1	r	(r-1 r-2 r-3 ... 0)
2r	nusum 2r	1	(r)

羃の列が(r-1 r-2 r-3 ... 0)のnusum (2^r-1) の式は

nusum (2^r-1) = (r-1)2^r-2 + (r-2+2)2^r-3 + (r-3+4)2^r-4 + ... + (0+2r-2)2^-1

で, これにrを足したものが

nusum 2^r = r.2^r-1

になればよい.

nusum (2^r-1)
={各項の係数の中を計算する}
(r-1)2^r-2+r2^r-3+(r+1)2^r-4+...+(r+(r-2))2^-1
={降順の羃の列で同じ係数を持つものをならべる}
(r-1)2^r-2+(r-1)2^r-3+(r-1)2^r-4+...+(r-1)2^-1  {1行目}
             +2^r-3+2^r-4+...+2^-1                    {2行目}
                    +2^r-4+...+2^-1                    {3行目}
                          +2^r-5+...+2^-1              {4行目}
                          +...
                          +2^-1                          {r行目}
={各行を2^p+2^p-1+... +2^q=2^p+1-2^q で置き換える}
(r-1)(2^r-1-2^-1)
+2^r-2-2^-1
+2^r-3-2^-1
+...
+2⁰-2^-1
={1行目を展開し2行目以下の第1項を足し合せる 2行目以下のr-1個の2^-1を足す}
(r-1)2^r-1-(r-1)2^-1+(2^r-1-2⁰) -(r-1)2^-1
={いろいろ消えて}
r2^r-1-2^r-1-(r-1)+2^r-1-1
=r2^r-1-r.

rを足せばnusum 2^rになる.

存外簡単であった.