递推的基础:证明当n = 1时表达式成立.
递推的依据:证明如果当n = m时成立,那么当n = m + 1时同样成立.
这种方法的原理在于第一步证明起始值在表达式中是成立的,然后证明一个值到下一个值的证明过程是有效的.如果这两步都被证明了,那么任何一个值的证明都可以被包含在重复不断进行的过程中.
或许想成多米诺效应更容易理解一些,如果你有一排很长的直立着的多米诺骨牌那么如果你可以确定：
第一张骨牌将要倒下,只要某一个骨牌倒了,与他相临的下一个骨牌也要倒,那么你就可以推断所有的的骨牌都将要倒.
这样就确定出一种递推关系,只要满足两个条件就会导致所有骨牌全都倒下：
（1）第一块骨牌倒下
（2）任意两块相邻骨牌,只要前一块倒下,后一块必定倒下
这样,无论有多少骨牌,只要保证（1）（2）成立,就会全都倒下.