十一、数学归纳法与抽屉原理

[数学归纳法] 对于包含整数n的公式,即从某一整数起对后面所有整数n都成立的公式,有时可用数学归纳法来证明.其步骤如下:

1o 验证n取第一个值n0时(如n0=0, 12等)公式成立.

2o 假定当n=k时公式成立,验证当n=k+1时公式也成立.

因为公式当n=n0时成立,所以由2o可知,当n=n0+1时公式也成立;再由2o可知,当n=n0+1+1=n0+2时公式也成立,如此继续推下去可知,对一切大于n0的整数n公式都成立.

[抽屉原理] n+1个物体放入n个抽屉里,至少有一个抽屉有两个以上的物体,这个原理称为抽屉原理,它在证明某些存在性定理时很有用.抽屉原理分以下三种形式:

1o n+1个元素分成n组,必有一组至少包含两个元素.

2o m个元素分成n(m>n为正整数),必有一组至少包含个元素([x]表示x的整数部分).

3o 无限多个元素分成有限组,必有一组包含无限多个元素.