式を整理する。Σのkは1からn-1。
n^3=n+6Σk(n-k)
n^4=n^2+12Σk^2(n-k)
n^5=n+30Σk^2(n-k)^2
n^6=n^2+60Σk^3(n-k)^2
n^7=10n/3+7n^3/3+140Σk^3(n-k)^3
Σの中身のべき乗が増えているので、べき乗部分をaとbと置いてS(a,b,n)を定義する。
S(a,b,n)=Σk^a(n-k)^b (Σのkは1からn-1) ... (1)
aとbは0以上の整数、nは2以上の整数を扱う。
離散的な畳み込みだったりベータ関数に似ている。
余談だけど、aとbの0以上の整数以外であっても、式としては成り立つ。
この式の性質として、aとbを入れ替えても等しい。
S(a,b,n)=S(b,a,n) ... (2)
Σの中身のkと(n-k)は1から順にn-1まで増えるかn-1から1まで順に減るかの違いで、kを1から増やすしてもn-1から減らしても合計は同じ。
それとΣの中身のkと(n-k)を足すとnになる。
n=k+(n-k) ... (3)
すると、こんな関係式をつくることができる。
nS(a,b,n)=S(a+1,b,n)+S(a,b+1,n) ... (4)
S(a,b,n)をΣの式に一度戻すとわかりやすい
nS(a,b,n)=nΣk^a(n-k)^b=Σnk^a(n-k)^b
=Σ(k+(n-k))k^a(n-k)^b
=Σk^(a+1)(n-k)^b+Σk^a(n-k)^(b+1)
S(a,b+1,n)について変形してみる。
S(a,b+1,n)=Σk^a(n-k)^(b+1)=Σk^a(n-k)^b(n-k)
=Σ(nk^a(n-k)^b-k^(a+1)(n-k)^b)
=nS(a,b,n)-S(a+1,b,n)
nS(a,b,n)の式をS(a,b+1,n)について解いた形と同じになりました。
nS(a,b,n)の、bがaと等しい(b=a)とすると
nS(a,a,n)=S(a+1,a,n)+S(a,a+1,n)=2S(a,a+1,n)
n^2S(a,a,n)だとどうか、
n^2S(a,a,n)=2nS(a,a+1,n)=2S(a+1,a+1,n)+2S(a,a+2,n)
aに0を代入してみる。
n^2S(0,0,n)=2S(1,1,n)+2S(0,2,n)
ちなみに、S(0,0,n)は1をn-1回足すのでn-1となる。
S(0,0,n)=Σk^0(n-k)^0=Σ1=n-1
S(0,2,n)＝Σk^2=n^3/3-n^2/2+n/6
左辺は
n^2(n-1)=n^3-n^2
右辺はS(1,1,n)をそのまま残して解くと
2S(1,1,n)+2(n^3/3-n^2/2+n/6)
両辺3倍して整理すると
n^3 = n + 6S(1,1,n) = n + 6Σk(n-k)
最初の式が求まった。
