求和公式

参考资料 《算法导论》

求和公式

A.1

∑k=1nk=12n(n+1)

A.3

∑k=1nk2=n(n+1)(2n+1)6

A.4

∑k=1nk3=n2(n+1)24

A.5

∑k=0nxk=xn+1−1x−1

A.6

∑k=0∞xk=11−x

其中 |x|<1

A.8

∑k=0∞kxk=x(1−x)2

其中 |x|<1

A.9

对于数列{a0..an}

∑k=1n−1(ak−ak−1)=an−a0

分析和证明

• A.1 ~ A.4都可以用归纳法证明，并不是很难

• A.5证明方法：设左边为S，求出xS，则xS−Sx−1=S等于右边。

• A.6：因为|x|<1，所以limn→∞xn+1=0

• A.8：A.6原式两面微分，两边乘x

• A.9：记得小学涉及过
  例如：∑n−1k=11k(k+1)=11×2+12×3...+1k(k+1)
  因为 1k(k+1)=1k−1k+1，所以对数列11,12...1k使用公式，得到
  

  ∑k=1n−11k(k+1)=∑k=1n−1(1k−1k+1)=1−1n
  
  也就是
  ∑n−1k=1(1k−1k+1)=11−12+12−13+13−14+...−1n−2+1n−2−1n−1