روش اول: سیگما
[tex]\sum^n_{i=1}\sum^n_{j=i}\sum^{j-1}_{r=1}1[/tex]
چرا کران بالای r برابر شده با j-1? چون r با k که مقدار j رو گرفته مقایسه میشه و چون تا زمانی که r<k مقایسه میشه پس به ازای r=j-1=k-1 هم درست هست و اجرا میشه.
چرا یک؟ چون مرتبه ی اجرای x++ برابر هست با ۱
ادامه ش:
[tex]\sum^n_{i=1}\sum^n_{j=i}\sum^{j-1}_{r=1}1=\sum_{i=1}^n\sum_{j=i}^n(j-1)[/tex]
مقدار داخلی ترین سیگما میشه از یک تا j-1 تا اجرا با هزینه ی ۱ که میشه j-1 تا اجرا با هزینه ی ۱
[tex]\sum^n_{i=1}\sum^n_{j=i}\sum^{j-1}_{r=1}1=\sum_{i=1}^n\sum_{j=i}^n(j-1)=\sum_{i=1}^n[(i-1)+(i+1-1)+(i+2-1)+(i+3-1)+...+(n-1)]=\sum^n_{i=1}[(i-1)+(i)+(i+2)+...+(n-1)]=\sum_{i=1}^n\frac{[n-1-(i-1)+1][n-1+(i-1)]}{2}=\sum^n_{i=1}\frac{[n-i+1][n+i-2]}{2}[/tex]
[tex]\sum^n_{i=1}\frac{[n-i+1][n+i-2]}{2}=\sum^n_{i=1}\frac{[n^2+ni-2n-ni-i^2-2+n+i+2i]}{2}=\frac{1}{2}\sum_{i=1}^n[n^2-i^2-n+3i-2]=[\frac{1}{2}\sum n^2-n-2-\sum i^2+3\sum i]=\frac{1}{2}[n\times(n^2-n-2)-\frac{n(n+1)(2n+1)}{2}+\frac{3n(n+1)}{2}][/tex]
[tex]\frac{1}{2}[n^3-n^2-2n-\frac{2n^3}{6}-\frac{3n^2}{6}-\frac{n}{6}+\frac{3n^2}{2}+\frac{3n}{2}]=\frac{1}{12}[6n^3-6n^2-12n-2n^3-3n^2-n+9n^2+9n]=\frac{1}{12}[4n^3-4n]=\frac{(n^3-n)}{3}[/tex]

روش دوم:
سوال تبدیل میشه به:
[tex]\frac{1}{2}\sum^n_{k=0}(n^2-n+k-k^2)=\frac{1}{2}[n^3-n^2]+\frac{1}{2}\sum^n_{k=0}k+\frac{1}{2}\sum k^2=\frac{(n^3-n^2)}{2}+\frac{(n+1)(n+2)}{4}-\frac{(n+1)(2n+3)(n+2)}{12}=\frac{[6n^3-6n^2+3n^2+9n+9n^2-12n-n-3n^2-2n^3]}{12}=\frac{[4n^3-4n]}{12}=\frac{[n^3-n]}{3}[/tex]