今天写一个算法题要计算某一表达式运行次数,一下子忘记了1的平方加2的平方一直加到n的平方的计算公式了,决定自己推导一下,于是发现可以有如下思路,记录如下:
Sn = 12 + 22 + 32 + …… + n2,求Sn
对Sn求导,发现函数的变化率为:
S’n = 2*1 + 2*2 + 2*3 + …… + 2*n = n(n+1)
于是发现Sn的导数是一个二次式,我们不妨假设Sn的表达式为:
Sn = a*n3 + b*n2 + c*n + d
将下列的四个结果代入解析式,去求a,b,c,d
n = 1,Sn = 1;
n = 2,Sn = 5;
n = 3,Sn = 14;
n = 4,Sn = 30;
最后求得:
a = 1/3
b = 1/2
c = 1/6
d = 0
于是得到:
Sn = (1/3)*n3 + (1/2)*n2 + (1/6)*n
最后再用假设演绎法推论当n = n+1 时也满足就行了