Recursive R(n)
if n==1 return 1;
else return R(n-1)+n*n*n
如何为该算法（n个立方体之和）设置和求解此递归关系？
最佳答案
表示S(n)第一个n立方体的和，S(n)必须是n中的四次多项式，让
S(n) = an^4+bn³+cn²+dn.
这是因为
1）
S(0)= 0，因此没有独立项，2）计算
S(n)-S(n-1)时，必须等于n³，通过取消四次项，可以得到三次多项式：S(n)-S(n-1) = a(n^4-(n-1)^4)+b(n³-(n-1)³)+c(n²-(n-1)²)+d(n-(n-1)).
发展和简化，
a(4n³-6n²+4n-1)+b(3n²-3n+1)+c(2n-1)+d = n³.
让我们确定系数：
n³: 4a =1
n²: -6a+3b =0
n: 4a-3b+2c =0
1: -a +b -c+d=0
求解这个三角形系统是一种策略：
a=1/4
b=1/2
c=1/4
d=0.
最后
S(n) = (n^4+2n³+n²)/4 = n²(n+1)²/4.
使用Faulhaber formula可以更简单，或者只考虑一个和是一个积分，而
n³的和大约是n^4/4。