程序员的数学--数学归纳法（0）
假设现在有一排多米诺骨牌，那么如何将他们推倒呢？
我们需要做到两点：
第一点：把第一个骨牌推倒
第二点：保证前一个骨牌可以把后一个骨牌推倒
而数学归纳法和多米诺骨牌有很多的相似之处。
接下来我们举一个例子
例子1：A(n)=nx2为偶数
由于当n=0时， 0x2=0，0是偶数，故条件成立
那么当n=1的情况呢， 1X2=2, 2是偶数，故条件成立
那么我们可以断言，对于0以上所有的整数n，命题都成立。
例子2：B(n)=nX3 都是偶数
当n=0时，0X3=0, 故条件是成立的
而当n=1时， 1X3=3， 而3是奇数，故命题不成立
那么我们可以看出，这样一个接着一个的判断是否太过繁琐了呢？
于是，我们在这里引出数学归纳法
数学归纳法是证明有关整数的断言对于0以上的所有整数是否成立时所用的方法。
步骤1：
证明 P(0) 成立
步骤2：
证明无论k为0以上的任意一个整数，都存在 P(k)成立，则P（k+1)成立。
步骤1，我们可以称其为基底（base)
步骤2,我们可以称作归纳（induction)
接下来，我们来看看一道例题
求出奇数的和
断言Q(n)：对于1以上的所有整数，都有
1+3+5+7+。。。+（2n-1)=n^2 成立
步骤1：基底的证明
证明Q(1)成立,
因为Q(1)=1=1^2
故基底证明完毕
步骤2：归纳的证明
我们假设Q(k)成立，即：
1+3+5+7+…+(2k-1)=k^2
则我们需要证明Q(k+1)
1+3+5+7+…+(2(k+1)-1)=(k+1)^2
Q(k+1)的左边=1+3+5+7+…+(2k-1)+(2(k+1)-1)
=k^2+2(k+1)-1
=k^2+2k+1
Q(k+1)的右边=（k+1)^2
=k^2+2k+1
左右计算相同
由此可得出Q(k)可以推出Q(k+1)
至此，我们可以说我们用数学归纳法推导出了断言Q(n)。证明这个断言是成立的
参考文献：
1.程序员的数学 【日】结成浩