如何用数学归纳法证明等式$n \geq 3$时$\sum\limits_{k=1}^{n-2}{n-k\choose 2}={n\choose 3}$
嘿，我来帮你搞定这个组合恒等式的证明！你之前用数学归纳法的时候把表达式搞乱了没关系，我给你准备了三种清晰的方法，从直观的计数思路到严谨的代数推导，还有理顺后的归纳法步骤，你可以按需参考～
我们先从组合数的本质——计数来理解：
- 右边的$\binom{n}{3}$，其实就是从n个不同元素里选出3个元素的总方案数。
- 再看左边的$\sum_{k=1}^{n-2}\binom{n-k}{2}$，咱先换个元，令$m = n - k$，当k从1跑到n-2时，m就从n-1降到2，所以左边可以改写为$\sum_{m=2}^{n-1}\binom{m}{2}$。
现在换个角度数右边的选3个元素的方案：假设我们选的3个元素里，最大的那个元素是$t$（t的取值范围是3到n，因为至少要两个比它小的元素才能凑成3个）。那剩下的两个元素必须从1到t-1里选，对应的方案数就是$\binom{t-1}{2}$。把所有可能的t值加起来，就是$\sum_{t=3}{n}\binom{t-1}{2}$，也就是$\sum_{m=2}{n-1}\binom{m}{2}$（令m=t-1），这正好就是左边的表达式！
所以左右两边其实是在算同一件事的方案数，自然相等～
如果喜欢用代数推导，我们可以把组合数展开成多项式求和：
首先，$\binom{m}{2} = \frac{m(m-1)}{2}$，所以左边的和可以写成：
$$
\sum_{m=2}^{n-1}\frac{m(m-1)}{2} = \frac{1}{2}\sum_{m=2}{n-1}(m2 - m)
$$
接下来用我们熟悉的求和公式：
- 等差数列求和：$\sum_{m=1}^{k}m = \frac{k(k+1)}{2}$，所以$\sum_{m=2}^{n-1}m = \frac{(n-1)n}{2} - 1$（减去m=1的项）
- 平方和公式：$\sum_{m=1}{k}m2 = \frac{k(k+1)(2k+1)}{6}$，所以$\sum_{m=2}{n-1}m2 = \frac{(n-1)n(2n-1)}{6} - 1$（减去m=1的项）
把这两个代入进去，里面的-1和+1会抵消，剩下：
$$
\frac{1}{2}\left[ \frac{n(n-1)(2n-1)}{6} - \frac{n(n-1)}{2} \right]
$$
提取公因式$\frac{n(n-1)}{6}$：
$$
\frac{1}{2} \times \frac{n(n-1)}{6} \left( (2n-1) - 3 \right) = \frac{n(n-1)}{12} \times (2n-4) = \frac{n(n-1)(n-2)}{6}
$$
而右边的$\binom{n}{3}$正好等于$\frac{n(n-1)(n-2)}{6}$，所以等式成立～
之前用归纳法卡壳可能是步骤没理清楚，咱重新一步步来：
- 基例验证：当n=3时，左边是$\sum_{k=1}^{3-2}\binom{3-k}{2} = \binom{2}{2} = 1$；右边是$\binom{3}{3} = 1$，等式成立。
- 归纳假设：假设当n=m（m≥3，m是整数）时，等式成立，即$\sum_{k=1}^{m-2}\binom{m-k}{2} = \binom{m}{3}$。
- 归纳递推：现在看n=m+1的情况，左边是$\sum_{k=1}^{(m+1)-2}\binom{(m+1)-k}{2} = \sum_{k=1}^{m-1}\binom{(m+1)-k}{2}$。
我们把这个和拆成两项：k=1的单独一项，加上k从2到m-1的部分：
$$
\binom{(m+1)-1}{2} + \sum_{k=2}^{m-1}\binom{(m+1)-k}{2} = \binom{m}{2} + \sum_{k'=1}^{m-2}\binom{m - k'}{2}
$$
这里令k'=k-1，后面的求和就是归纳假设里的$\binom{m}{3}$，所以左边变成$\binom{m}{2} + \binom{m}{3}$。
还记得组合数的递推公式吗？$\binom{m}{r} + \binom{m}{r+1} = \binom{m+1}{r+1}$，这里r=2，所以$\binom{m}{2} + \binom{m}{3} = \binom{m+1}{3}$，正好等于n=m+1时右边的$\binom{m+1}{3}$。
这样就完成了归纳递推，所以对所有n≥3，等式都成立。
内容的提问来源于stack exchange，提问作者Christian Singer
