本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
知识点
- 帕斯卡恒等式
题目
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.
分析
这是二项式定理的一个运用
二项式定理可以用以下公式表示：
其中
又有
等记法，称为二项式系数(binomial coefficient)，即取的组合数目。此系数亦可表示为杨辉三角形。它们之间是互通的关系。 根据该定理，可以将多项式（x + y）n 扩展为涉及axbyc形式的和的总和，其中指数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 =
假设当k = 4,5,6,7.....N 时成立，即 f(k) =
则 k = N+1 时，先去其中 N 个数，即 f(N)，再取其中N个数与余下一个组合，则共有，所以f(N+1) = f(N) +
=
,得证
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
