证明最小乘数问题，解空间一共被引用的次数

Let R(i, j) be the number of times that table entry m[i, j] is referenced while computing other table entries in a call of MATRIX-CHAIN-ORDER. Show that the total number of references for the entire table is




证明，靠，太简单了，就是算个sigma。
R(i, j) = i - 1 + (n - j)，sigma(i = 1..n):sigma(j = i..n):(i - 1 + n - j)
= sigma(i = 1..n):sigma(j = i..n):[(n-1) + i - j]
= s(i=1..n):s(j=i..n):(n-1) + s(i=1..n):s(j=i..n):i - s(i=1..n):s(j=i..n):j
= s:(n2 - 1 - n*i + i) + s:(n *i - i*i + i) -s:(n2 - i2 + n + i)/2
=n3-n-n*s:i +s:i +n*s:i -s:i2 - s:(n2+n)/2 + s:i2/2 -s:i/2
=n3 - n +(3/2) *s:i - (1/2)*s:i2 - (n3+n2)/2
= n3/2 -n - n2/2 + (3/4)*n2 + (3/4)n - (n2+n)(2*n + 1)/12
= n3/3 - n/3

可是算了我这么长时间，妈妈的。