题目取自：《数据结构与算法分析:C语言描述_原书第二版》——Mark Allen Weiss

练习1.5(a)  证明下列公式: logX < X 对所有 X > 0 成立。(注意：计算机科学中，若无特别说明，所有对数都是以2为底的)

　　这个小题，看似简单。乍一看一高中证明题而已嘛。实则不然，我根据高中时常用的思路解了一下:

　　　　　　设 f(X) = X - logX，其中X > 0。  

　　　　　　易知 f(0) = 0 + ∞ > 0，f(X)′ = 1 - 1/(Xln2)，令f(X)′ = 0，解得X = 1/ln2。

　　　　　　于是当 0< X < 1/ln2时，f(X)′ < 0，函数单调递减。

　　　 　　  X > 1/ln2时，f(x)‘ > 0，函数单调递增。

所以f(1/ln2)为函数的极小值点。到这里我们只需要求出 f(1/ln2) = 1/ln2 - log(1/ln2) > 0 问题就得证了。结果的确大于零，不过计算结果只得求助于计算器(对减数进行放大也行不通)。对于求助于计算器的问题多少让人感觉不爽。到这里才想到，高中应该做的是lnX < X，问题一下就得到了可靠的答案(这里可靠的意思：不用借助计算器)。

我带着这个多少让人不爽的问题到网上搜了一圈，也没有多大的收获，很多还是错误的。不得已网搜了一下题解，发现本书竟然有作者提供的答案，于是果断搬了过来:)

不得不说Mark Allen Weiss，不得不说人家美国名流写的书啊，反观国内某些数据结构方面的书弱爆了有木有！不多说了，赶紧随我来膜拜一下Weiss吧：

证明采用数学归纳法。

　　0 < X ≤ 1 时，logX < X 显然成立。因为X = 1时，log1 = 0 < 1。X < 1时，logX为负数，明显小于X。

　　同样显然的情况是1 < X ≤ 2 时。因为log2 = 1 < 2，且X < 2 时logX < 1。

准备好了，最精彩的部分来了：

　　归纳基础：1< X ≤ 2 时命题成立，由上可知。

　　归纳假设：假设命题对任意正整数p(p≥1)，p < X ≤ 2p 时命题成立，求证对于任意的正整数p，2p < Y < 4p命题成立。

　　证明：logY = log(2·y/2) = log2 + log(y/2) = 1 + Y/2 < Y/2 + Y/2 ≤ Y。

　　　　　即logY < Y成立。

　　数学归纳法的步骤是完美的，因此命题logX < X，X > 0成立。

PS:由于答案是英文的，这里对语序做了下调整，且对不易理解的部分做了补充。

证明 logX < X 对所有 X > 0 成立