算法练习(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.

分析

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

二项式定理可以用以下公式表示：

其中
又有
等记法，称为二项式系数(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成立
假设当k = 4,5,6,7.....N时成立，即k(k-1)(k-2)/6

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。