数学归纳法初探

数学归纳法简介

数学归纳法（Mathematical Induction, MI）是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。

数学归纳法在计算机科学中广泛应用，例如用代入法解递归式、用循环不变式证明算法正确性等。深刻理解数学归纳法有利于建立良好的递归逻辑，对于动态规划、分治法、搜索法都十分有利。
在初中数学题目中，也有一些可以用数学归纳法解决。最后将给出一道这样的例题。

例题1 ：奇数和奇数的性质

奇数通常被这样定义：

1是奇数
如果n是奇数，那么n+2是奇数

或者形式化地定义集合F = {1,n+2 | n ∈ F}为奇数集合。显然，对于任意一个奇数n，它的后一个奇数为n+2；对一个不为1的奇数n，它的前一个奇数为n-2。（性质1）
不妨将所有奇数从小到大排成一列，排在第n位的成为第n个奇数。显然，这个数列是{1,3,5,7,9...}。经过特例归纳，我们发现，第n个奇数恰好等于2n-1。这是不是一个巧合呢？我们将用数学归纳法结合定义和性质1，证明这个结论。

性质2 ：第ｎ个奇数的值为２ｎ－１

证明：不妨将第n个奇数称为F(n)，定义函数y = P(n) = 2n-1，证明对于任意n>1且n∈N，总是有F(n) = P(n)

当n = 1时，F(1) = P(1) = 2n-1 = 1，显然正确

对于任何一个大于1的n，如果F(n-1) = P(n-1)，那么F(n) = P(n)

已知：F(n-1) = P(n-1)
求证：F(n) = P(n)
证明： 
    ∵ F(n-1) = P(n-1) = 2(n-1)-1 = 2n-3
    ∴ F(n) = F(n-1) + 2 = 2n-1 (性质1)
    ∵ P(n) = 2n-1
    ∴ F(n) = P(n) (等量代换)

原式得证。
这个例子揭开了数学归纳法神奇的一角：我们证明了F(1) = P(1)，又证明了对于F(n-1) = P(n-1)成立时，F(n) = P(n)也成立，从而证明了原命题。由此可见，数学归纳法是一种递推的思想，通过一个基本情况和一个递推情况把结果推广到所有自然数。

性质3：前n个奇数的和为n^2

首先特例归纳之：设S(n) = F(1) + F(2) + F(3) + … + F(n)，有如下关系：

函数	数据	数据	数据	数据	数据	数据
F(n)	1	3	5	7	9	…
S(n)	1	4	9	16	25	…
y = n^2	1	4	9	16	25	…

特例归纳发现 S(n) = n^2。下面证明这个结论：

已知：设S(n) = sigma{F(i) | 1≤i≤n且i∈N}，y = T(n) = n^2
求证：S(n) = T(n)
证明：

当n = 1时，T(1) = 1 = F(1) = S(1)，显然正确

对于任何一个大于1的n，如果S(n-1) = T(n-1)，那么S(n) = T(n)

已知：S(n-1) = T(n-1)
求证：S(n) = T(n)
证明：
    ∵ S(n-1) = T(n-1) = (n-1)^2 = n^2-2n+1
    ∵ S(n) = S(n-1) + F(n) (显然)，F(n) = 2n-1 (性质2)
    ∴ S(n) = (n^2-2n+1) + (2n-1) = n^2
    ∵ T(n) = n^2
    ∴ S(n) = T(n) (等量代换)

原式得证。
到这里为止，我们已经利用数学归纳法证明了奇数的两个性质，对“归纳”有了较深刻的含义。但是这种归纳不限于数的问题，许多几何的找规律也需要数学归纳法。

例题2：几何找规律

设有一正方形ABCD边长为1，ABCD的面积记作A(1)；以ABCD的对角线AC为边长作正方形ACEF，面积记作A(2)；以ACEF的对角线AE为变长作正方形AEGH，面积记作A(3)……由此类推，求A(2015)

不妨特例归纳之：

函数	数据	数据	数据	数据	数据
n	1	2	3	4	…
A(n)	1	2	4	8	…

不难发现，A(n) = 2^(n-1)。下面证明它：

证明：设y = Q(n) = 2^(n-1)

当n = 1时，A(1) = 1 = Q(2)，显然正确
对于任何一个大于1的n，如果A(n-1) = T(n-1)，那么S(n) = T(n)
已知：A(n-1) = Q(n-1)
求证：A(n) = Q(n)
证明：由于A(n)的边长为√2A(n-1)，A(n) = [√2A(n-1)]^2 = 2A(n-1)
∵ A(n-1) = Q(n-1) = 2^(n-2)
∵ A(n) = 2A(n-1)
∴ A(n) = 2^(n-2) * 2 = 2^(n-1) = Q(n)

原式得证。
更一般的，这个证明可以推理等比数列通项公式，请各位自己试一试。

练习

用归纳法证明：对于F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}，F(n)是斐波那契数列的第n项
用归纳法证明：
1. 等差数列的通项公式：
2. 等差数列求和公式：