数据结构分析中最常用的两种证明方法就是归纳法和反证法。
反证法顾名思义，没有任何疑问。
但是归纳法为什么要分成两步？为什么通过这两步就能说明结论正确呢？
归纳法总体上分为两步:第一步证明基本情况i=1结论正确；第二步先假设i=k结论正确，然后通过假设证明i=k+1结论也是正确的。
对于第二步一般都没有疑问，但是为什么需要对基本情况进行验证呢？这是因为，只有基本情况i=1结论正确，才能通过第二步的递推，腿出i=2, i=3,i=4,...i=N是正确的。否则，如果连节本情况正确与否，仅仅通过证明递推，是没法证明结论是正确的。
原文：https://www.cnblogs.com/chaoguo1234/p/13198564.html