算法练习(54): 二项式定理证明(1.4.1)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

帕斯卡恒等式

题目

1.4.1 证明从N个数中取三个整数的不同组合为 N(N-1)(N-2)/6. 提示：使用数学归纳法

1.4.1 Show that the number of different triples that can be chosen from N items is precisely N (N 1)(N 2)/6. Hint : Use mathematical induction.

分析

这是二项式定理的一个运用

二项式定理可以用以下公式表示：
${(a+b)^n} = \sum_{r=0}^{n}{C_n^r}a^{n-r}b^r$
其中 $C^r_n = \frac{n!}{r!(n-r)!}$
又有

等记法，称为二项式系数(binomial coefficient)，即取的组合数目。此系数亦可表示为杨辉三角形。它们之间是互通的关系。根据该定理，可以将多项式（x + y）ⁿ 扩展为涉及ax^by^c形式的和的总和，其中指数b和c是具有b + c = n的非负整数，并且系数a 每个项是根据n和b的特定正整数。

题目要求使用数学归纳法，那么什么是数学归纳法呢

数学归纳法（Mathematical Induction, MI）是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，例如：集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域，称作结构归纳法。

证明流程

最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：
1.证明当n= 1时命题成立。
2.假设n=m时命题成立，那么可以推导出在n=m+1时命题也成立。（m代表任意自然数）这种方法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺效应也许更容易理解一些。

答案

当k=3时，N(N-1)(N-2)/6 = 1成立，f = $\frac{(3-1)(3-2)}{6}$
假设当k = 4,5,6,7.....N 时成立，即 f(k) = $\frac{(k-1)(k-2)}{6}$
则 k = N+1 时，先去其中 N 个数，即 f(N)，再取其中N个数与余下一个组合，则共有 $\frac{(N-1)(N-2)}{2}$ ，所以f(N+1) = f(N) + $\frac{(N-1)(N-2)}{2}$ = $\frac{(N-1)N(N+1)}{6}$ ,得证