たし算とかけ算の間には

$\displaystyle{+++\cdots+=\times}$

という関係がありますが(伝われ)、実はこれが $\sum$ と $\prod$ にも言えそうなのです。つまり

$\displaystyle{\sum\sum\sum\cdots\sum=\prod}$

も言えそう、という感じ。
これは自分で作った問題を解く過程で発見したもので、先に予想が立ってから証明しました。必要は発明の母とはよく言ったものですね。

まずは結果から

結果から言うと、こうなります。

定理1 $\displaystyle{\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_1=1}^{a_2}1=\frac{1}{(n-1)!}\prod_{i=1}^{n-1}({a_n}+i-1)}$

ゴツい。

等号の左右で見比べてみると、 $n-1$ 個あった $\sum$ がたった1個の $\prod$ にまとまっています。嬉しいです。
これが成り立つことを示します。そう、みんな大好き証明タイムです。

補題ってかっこいい

定理1を示すにあたり、以下の補題を考えます。

補題 $\displaystyle{\sum_{j=1}^{J}\prod_{i=1}^{r}(j+i-1)=\frac{1}{r+1}\prod_{i=1}^{r+1}(J+i-1)}$

$\sum$ が消えています。あとでこれを繰り返し使うことで $\sum$ をまとめていくので、これが本質的な部分です。
以下の補題の証明は昔どこかのサイトで見たもののほぼそのままです。どこだったか覚えがなくてリンクを貼れないこと、引用元を明示できないことが残念ですが、必要なので使わせていただきます。どなたか心当たりがある方は教えていただけるとありがたいです。

証明

$\displaystyle{f_r(j)=\prod_{i=1}^{r}(j+i-1)}$

とおくと

$\displaystyle{f_r(j)=\frac{(j+r)-(j-1)}{r+1}\prod_{i=1}^{r}(j+i-1)\\ =\frac{1}{r+1}(\prod_{i=1}^{r+1}(j+i-1)-\prod_{i=0}^{r}(j+i-1))\\ =\frac{1}{r+1}(f_{r+1}(j)-f_{r+1}(j-1))}$

なので

$\displaystyle{\sum_{j=1}^{J}f_r(j)=\sum_{j=1}^{J}\frac{1}{r+1}(f_{r+1}(j)-f_{r+1}(j-1))\\ =\frac{1}{r+1}(f_{r+1}(J)-f_{r+1}(0))}$

となる。ところで

$f_{r+1}(0)=0$

なので

$\displaystyle{\sum_{j=1}^{J}f_r(j)=\frac{1}{r+1}f_{r+1}(J)}$

元の記号に戻すことで

$\displaystyle{\sum_{j=1}^{J}\prod_{i=1}^{r}(j+i-1)=\frac{1}{r+1}\prod_{i=1}^{r+1}(J+i-1)}$

が得られた。

(証明終わり)

定理1の証明

続いて定理1の証明です。めちゃくちゃゴツいです。

証明

$\displaystyle{\sum_{a_1=1}^{a_2}1=a_2=\frac{1}{1!}\prod_{i=1}^{1}(a_2+i-1)}$

なので

$\displaystyle{\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_1=1}^{a_2}1}$

$\displaystyle{=\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_2=1}^{a_3}\frac{1}{1!}\prod_{i=1}^{1}(a_2+i-1)}$

ここで補題で示した恒等式を使うと

$\displaystyle{\sum_{a_2=1}^{a_3}\frac{1}{1!}\prod_{i=1}^{1}(a_2+i-1)}$

$\displaystyle{=\frac{1}{1!}\sum_{a_2=1}^{a_3}\prod_{i=1}^{1}(a_2+i-1)}$

$\displaystyle{=\frac{1}{1!}\frac{1}{1+1}\prod_{i=1}^{2}(a_3+i-1)}$

$\displaystyle{=\frac{1}{2!}\prod_{i=1}^{2}(a_3+i-1)}$

これを繰り返し適用することで

$\displaystyle{\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_2=1}^{a_3}\frac{1}{1!}\prod_{i=1}^{1}(a_2+i-1)}$

$\displaystyle{=\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_3=1}^{a_4}\frac{1}{2!}\prod_{i=1}^{2}(a_3+i-1)}$

$\displaystyle{=\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_u=1}^{a_{u+1}}\frac{1}{(u-1)!}\prod_{i=1}^{u-1}(a_u+i-1)}$

$\displaystyle{=\sum_{a_{n-1}=1}^{a_n}\frac{1}{(n-2)!}\prod_{i=1}^{n-2}(a_{n-1}+i-1)}$

$\displaystyle{=\frac{1}{(n-2)!}\sum_{a_{n-1}=1}^{a_n}\prod_{i=1}^{n-2}(a_{n-1}+i-1)}$

$\displaystyle{=\frac{1}{(n-1)!}\prod_{i=1}^{n-1}({a_n}+i-1)}$

(証明終わり)

ここまででタイトルの連続するΣをΠでまとめるはできました。

このままでも＋と $\times$ との関係として十分面白いのですが、よく見ると一番右の $\sum$ は1をたしています。これではつまらないので、実用性を与えるために定理1を拡張します。

どんな数列でも足せる

定理1では1を足していました。定理1を拡張した定理2では任意の数列を足せるようにします。

定理2 任意の数列 $\{A_n\}$ に対して
$\displaystyle{S_A(a_n)=\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_1=1}^{a_2}A_{a_1}}$
とすると
$\displaystyle{S_A(a_n)=\sum_{a_{n-1}=1}^{a_n}{}_{a_n-a_{n-1}+n-2}C_{n-2}A_{a_{n-1}}}$

$\prod$ がありませんが、内部では $\sum$ がまとめられています。なので証明の中で定理1の証明で使った補題を再利用します。
紛らわしいですが、数列 $\{A_n\}$ と添字数列 $\{a_n\}$ は全く関係のないものであることに注意してください。
また、 $\{a_n\}$ を形式的に数列ということにしましたが、これは定理の形の都合で $a_n$ から自然に定義されるもので、自動的に $a_{k-1}\leq a_k$ となります。Σが並んでいるので、区別のために添字数列のようにまとめて扱いましたが、本来的に数列である必要性はありません。
よって、形式的な入れ替えが可能です。

定理2の証明

帰納法で示す。

ステップ1　 $n=2$ のとき

$\displaystyle{S_A(a_2)=\sum_{a_1=1}^{a_2}A_{a_1}=\sum_{a_1=1}^{a_2}{}_{a_2-a_1+2-2}C_{2-2}A_{a_1}}$

ステップ2　 $n=k$ のとき成り立つと仮定

すると $n=k+1$ のとき

$\displaystyle{S_A(a_{k+1})=\sum_{a_k=1}^{a_{k+1}}S_A(a_k)\\=\sum_{a_k=1}^{a_{k+1}}\sum_{a_{k-1}=1}^{a_k}{}_{a_k-a_{k-1}+k-2}C_{k-2}A_{a_{k-1}}}$

$A$ の添字である $a_{k-1}$ を固定して足す順番を変えると、定義から $a_k \geq a_{k-1}$ なので、

$\displaystyle{\sum_{a_{k-1}=1}^{a_{k+1}}\sum_{a_k=a_{k-1}}^{a_{k+1}}{}_{a_k-a_{k-1}+k-2}C_{k-2}A_{a_{k-1}}}$

$a_{k-1}$ と $a_{k}$ を形式的に入れ替えることで、

$\displaystyle{\sum_{a_k=1}^{a_{k+1}}\sum_{a_{k-1}=a_k}^{a_{k+1}}{}_{a_{k-1}-a_k+k-2}C_{k-2}A_{a_k}}$

$\displaystyle{=\sum_{a_k=1}^{a_{k+1}}\sum_{a'_{k-1}=1}^{a_{k+1}-a_k+1}{}_{a'_{k-1}-1+k-2}C_{k-2}A_{a_k}}$

このとき、入れ替えによって $a_k \leq a_{k-1}$ となります。ここで $a_{k-1}'=a_{k-1}-a_k+1$ のように置き換えているので、 $a'_{k-1}\geq 1$ となりますが、自然とその条件を満たしていることがわかります。

式変形を続けると、

$\displaystyle{=\sum_{a_k=1}^{a_{k+1}}\sum_{a'_{k-1}=1}^{a_{k+1}-a_k+1}\frac{(a'_{k-1}-1+k-2)!}{(a'_{k-1}-1)!(k-2)!}A_{a_k}}$

$\displaystyle{=\sum_{a_k=1}^{a_{k+1}}A_{a_k}\sum_{a'_{k-1} =1}^{a_{k+1}-a_k+1}\frac{1}{(k-2)!}\prod_{i=1}^{k-2}(a'_{k-1} +i-1)}$

ここで補題を適用すると

$\displaystyle{\sum_{a_k=1}^{a_{k+1}}A_{a_k}\sum_{a'_{k-1} =1}^{a_{k+1}-a_k+1}\frac{1}{(k-2)!}\prod_{i=1}^{k-2}(a'_{k-1} +i-1)}$

$\displaystyle{=\sum_{a_k=1}^{a_{k+1}}A_{a_k}\frac{1}{(k-1)!}\prod_{i=1}^{k-1}(a_{k+1}-a_k+i)}$

$\displaystyle{=\sum_{a_k=1}^{a_{k+1}}\frac{(a_{k+1}-a_k+k-1)!}{(a_{k+1}-a_k)!(k-1)!}A_{a_k}}$

$\displaystyle{=\sum_{a_k=1}^{a_{k+1}}{}_{a_{k+1}-a_k+k-1}C_{k-1}A_{a_k}}$

(証明終わり)

これで定理1の拡張版である定理2が得られました。任意の数列を好きなだけ足し上げることができます。

ステップ2で足す順番を変えるところは、具体的に表を書いてみるとわかりやすいです。あとは技術的な問題なので、式をいじくり回すだけです。

実際に使ってみる

せっかくなので、フィボナッチ数列を例に定理2を使ってみます。

$\{A_n\}=1,1,2,3,\cdots$ 、 $a_4=5$ 、とすると

愚直に足す

$\displaystyle{\sum_{a_3=1}^{5}\sum_{a_2=1}^{a_3}\sum_{a_1=1}^{a_2}A_{a_1}}$

$=A_1$

$+\{A_1+(A_1+A_2)\}$

$+\{A_1+(A_1+A_2)+(A_1+A_2+A_3)\}$

$+\{A_1+(A_1+A_2)+(A_1+A_2+A_3)+(A_1+A_2+A_3+A_4)\}$

$+\{A_1+(A_1+A_2)+(A_1+A_2+A_3)+(A_1+A_2+A_3+A_4)+(A_1+A_2+A_3+A_4+A_5)\}$

$=1+3+7+14+26=51$

定理2を使う

$\displaystyle{S_A(a_4=5)=\sum_{a_3=1}^{5}{}_{5-a_3+4-2}C_{4-2}A_{a_3}}$

$={}_{6}C_{2}A_1+{}_{5}C_{2}A_2+{}_{4}C_{2}A_3+{}_{3}C_{2}A_4+{}_{2}C_{2}A_5$

$=15+10+12+9+5$

$=51$

一致しました。定理2を使った方がずっと楽に計算できました。素晴らしいです。

追記(2019/12/01)
先日大学で友達と一緒にお昼を食べていたら、
「特定のfor文のネストを線形時間で解けるようになる高速化アルゴリズムなんじゃない？」
という話が上がりました。
使う場面がどれだけあるかはさておいて、確かにm重ループの計算がO(N^m)からO(N)に削減できている気がします。
なかなか良い結果が得られたなぁとニヤニヤを深めました。

ぺるせんたげの学習帳

手作り数学のブログです

連続するΣをΠでまとめる

まずは結果から

補題ってかっこいい

証明

定理1の証明

証明