一乗和
1+2+3+ \cdots +n
の和を求めよ、という問題を解く時に、いちいちすべての項を計算する必要はありません。
\frac{1}{2}n(n+1)
という形で高速計算できることは広く知られており、高校数学でも教えられます。
これをわかりやすく可視化すると以下のようになると思われます。
求めたい値はこの 疑似直角三角形 であり、それらをうまく組み合わせて 長方形 を作ることによって計算できます。
二乗和
1+2^2+3^2+ \cdots +n^2
についても、同様に
\frac{1}{6}n(n+1)(2n+1)
で計算できることが知られています。これは可視化できるでしょうか？
類推して考えれば、これは 疑似四角錐 をうまく組み合わせて 直方体 を作ることによって計算できます。
結論から言えばこれは可能であり、以下のような形になります。
ただ、これを頭の中でスムーズにイメージできる人は稀だと思います。筆者も、3D モデリングソフトと格闘しながら上の動画を作りました。
三乗和
大学受験でも使うかどうかというレベルですが、一応、三乗和も
1+2^3+3^3+ \cdots +n^3 = \frac{1}{4}n^2(n+1)^2
これはなぜかキレイな形になってとても覚えやすいです。
これもスマートな可視化の方法があります。
黄色の部分に重複がありますが、右上に隣接した部分と相殺するので、求めたい値はこの巨大な正方形のそれと一致します。
この可視化の方法については、いつか旧 Twitter で見かけたのですが、リンクを失念してしまいました。元ツイート（当時）をみつけたり、体系的にまとまっているページがあれば、そこへのリンクを追記しておきます。とりあえず、私のオリジナルではないことは記しておきます。
ちなみに、四乗和以降もキレイな形になってくれたら嬉しいですが、残念ながらそうはならず、一般化にはベルヌーイ数を使った複雑な計算が必要です。
二乗和の別の方法
先日、旧 Twitter を見かけていたら、二乗和の可視化に関するスマートな別の方法をみかけました。そのエッセンスを筆者なりに解釈して図にしたものがこちらになります。
めちゃくちゃ覚えやすい！
これの一般化
これを一般化したら、複雑な $k$ 乗和に関する一般式がもう少しシンプルに表現できるのでは？
そんな野心が芽生えたので、ちょっと考えてみました。
まず、$L$ 次元におけるひとつの項は、以下のようになります。
- $1$ 次元のとき、$[(1),(2),(3),(4),(5),\cdots]$
- $2$ 次元のとき、$[(1),(2,2),(3,3,3),(4,4,4,4),(5,5,5,5,5),\cdots]$
- $3$ 次元のとき、$[(1),(2,2,2),(3,3,3,3,3,3)\cdots]$
幾何的な理解としては、$1$ 次元のときは線分、$2$ 次元のときは正三角形、$3$ 次元のときは正四面体に、$1\sim n$ の数をわりあてたものになります。
$L$ 次元において、このような最小構成立体は 単体（simplex） と呼ばれます。単体に $1\sim N$ の数をわりあてたものなので、これらの各項を $L$ 次元における長さ $n$ の 重み付き単体（weighted simplex） と定義し、その総和を $W_{L,n}$ とします。
線分（$L=1$）や正三角形（$L=2$）がそれぞれ等しく重ね合わせられたように、$L$ 次元における重み付き単体も等しく重ね合わせられます。
証明
$L=3$ のときの証明を載せる。これは任意の高次元に自然に拡張できる。
以下 $4$ つの重み付き四面体を定義する。重みの定義は、
- $f_0(x,y,z) = x+y+z-2$
- $f_1(x,y,z) = n-x+1$
- $f_2(x,y,z) = n-y+1$
- $f_3(x,y,z) = n-z+1$
であり、いずれの四面体においても、重みは以下の領域においてのみ定義される
- $x\geq1$
- $y\geq1$
- $z\geq1$
- $x+y+z\leq n$
これらの四面体のすべての合計の重みは、以下になる
- $f_{\text{all}}(x,y,z) = 3 \cdot n+1$
（証明終）
上の「別解」で示されたアイデアを一般化すると以下のようになります。
(L+1)W_{L,n} = (L\cdot n+1) S_{L,n}
ここで、$S_L$ は $L$ 次元単体に含まれる要素の数です。
これは、
- $S_{0,n} = 1+1+1 \cdots +1$
- $S_{1,n} = 1+2+3 \cdots +n$
- $S_{2,n} = 1+3+6 \cdots +\sum_{i=1}^{n} S_{1,i}$
$\vdots$
となるので、逐次計算が必要になるかと思いきや、二項係数で一気に計算できます。
S_{L,n} = _{L+n}C_{L+1}
結論
$L$ 次元における長さ $n$ の重み付き単体の総和 $W_{L,n}$ は以下の計算式により計算できる。
W_{L,n} = \frac{L \cdot n+1}{L+1}\cdot _{L+n}C_{L+1}
なお、$L=1$ および $L=2$ のとき、$W_{L,n}$ は $L$ 乗和と一致する。
- $W_{1,n} = \frac{n+1}{2}\cdot n = \frac{1}{2}n(n+1)$
- $W_{2,n} = \frac{2 \cdot n+1}{3} \cdot \frac{1}{2}n(n+1) = \frac{1}{6}n(n+1)(2n+1)$
- $W_{3,n} = \frac{3 \cdot n+1}{4} \cdot \frac{1}{6}n(n+1)(n+2) \neq \frac{1}{4}n^2(n+1)^2$
補足
上の結論からわかる通り、この公式は $3$ 乗以上の累乗和を求めるのには役に立ちません。残念！