巧用组合数证明平方和、立方和 - Fighlone
巧用组合数证明平方和、立方和
前言：搞算法，做数学，求和的时候往往会遇到平方求和，立方求和。但是求和的公式并不是那么好背，网上搜一搜都是千篇一律的三次方差，四次方差相减求和相消，一堆数字看着人头皮发麻。。。
而用组合数就灵活得多~
证明1（平方求和）： $\sum_{i = 1}^{n}\left(i^{2}\right)=\sum_{i=1}^{n}\left[i\times (i-1)+i\right]$
$=2\sum_{i=1}^{n}\left[\frac{i\times(i-1)}{1\times 2}\right] + \sum_{i=1}^{n}i$
$=2\sum_{i=2}^{n}C_{i}^{2} + \sum_{i=1}^{n}i$ （这里的组合数求和方法高中至少学过四种）
$=2\times C_{n+1}^{3}+ \frac{n \times (n+1)}{2}$
$=\frac{n\times(n+1)\times(2n+1)}{6}$
证明2（立方求和)(方法同上类似)： $\sum_{i=1}^{n}i^{3}=\sum_{i=1}^{n}\left[i^{2}\times (i+1) – i^{2}\right]$
$=\sum_{i=1}^{n}\left[ i\times(i+1)\times(i-1+1) – i^{2}\right]$
$=\sum_{i=1}^{n}\left[ (i-1)\times i\times(i+1) +i\times(i+1)- i^{2}\right]$
$=6\times\sum_{i=2}^{n}C_{i+1}^{3}+2\times\sum_{i=1}^{n}C_{i+1}^{2}-\sum_{i=1}^{n}i^{2}$ (这里就用到了证明1的平方求和结论)
$=6\times C_{n+2}^{4} + 2 \times C_{n+2}^{3}-\frac{n\times(n+1)\times(2n+1)}{6}$
$=\frac{(n+2)\times(n+1)\times n\times(n-1)}{4}+\frac{(n+2)\times (n+1)\times n}{3} -\frac{n\times (n+1)\times (2n+1)}{6}$
$=\left[\frac{n\times(n+1)}{2}\right]^{2}$
总结： 很巧妙，本来无从下手的式子，化成组合数的形式再求和就变得迎刃而解。
而究其组合数的本质，这个东西说白了不就是由加减乘除这些基本的运算组成的吗，但是“组合”起来就有了它自己的性质。
这和OOP的思想有异曲同工之妙，或许为我们以后解决问题提供了更高一阶的角度。