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

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

1^o 验证n取第一个值n₀时(如n₀=0, 1或2等)公式成立.

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

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

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

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

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

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