测试 Latex 显示

补记：因更换主题，懒得再改 JS 文件，故此文显示不正常。

自然 eqnarray 这些 ams 宏包带的命令是不能用的了，式子对齐变得很有挑战。\prime 也用不了。字号跟文档中的字体是一样大小的，阅读起来比较困难，不过可以通过加属性使之变得更大一些。浏览以及打印效果会依赖客户端的浏览器，支持 MathML 标准的浏览器（如 Firefox）会比较清晰，如果是 IE 的话（且没有安装 MathML 插件）显示的是图片，打印效果估计会很糟糕。

引用：如何在科学空间输入数学公式？——LaTeX 帮助

有兴趣可以查看一下页面的源代码以及页面的 MathML 源代码。

附：（算法导论第十章思考题 10-3）

c) 证明：$E[X_t]\le \sum_{r=1}^n(1-r/n)^t$

假设所需关键字的位置为 k，则链表中从位置 i 到所需关键字的期望距离为 $E[X_t^{‘}]$，则有 (其中 $Pr(d=r)$的意思是距离 d 为 r 的概率 Probability 的缩写)

这段是加大字号的

$E[X_t^’] = \sum_{r=0}^{k-1}r \cdot Pr(d=r) $
$=\sum_{r=1}^{k-1}r\cdot(Pr(d \ge r)-Pr(d \ge r+1)) $
$=\sum_{r=1}^{k-1}Pr(d \ge r) – r \cdot Pr(d \ge k)$
$\le\sum_{r=1}^{k-1}Pr(d \ge r) $
$=\sum_{r=1}^{k-1}(1-r/n)^t$

而 k 的位置可以在 1 到 n 中随机取，则有：

$E[X_t]=\sum_{i=1}^n \frac{1}{n}E[X_t^’] $
$\le\sum_{i=1}^n \frac{1}{n}\sum_{r=1}^{k-1}(1-r/n)^t $
$\le\sum_{r=1}^n(1-r/n)^t$

证毕。

d) 证明：$\sum_{r=0}^{n-1}r^t\le n^{t+1}/(t+1)$

使用归纳法，当 n=1 时，不等式显然成立。
假设 n=n-1 时，有 $\sum_{r=0}^{n-2}r^t \le (n-1)^{t+1}/(t+1)$，则 n=n 时，有：

$\sum_{r=0}^{n-1}r^t = \sum_{r=0}^{n-2}r^t + (n-1)^t $
$\le(n-1)^{t+1}/(t+1) + (n-1)^t $
$=(n-1)^t\frac{n+t}{t+1}$

而要证 $\sum_{r=0}^{n-1}r^t\le n^{t+1}/(t+1)$，即证：$(n-1)^t\frac{n+t}{t+1} \le n^{t+1}/(t+1)$

即证：$(n-1)^t(1+t/n)\le n^{t}=(n-1+1)^{t}=(n-1)^t+t(n-1)^{t-1}+\ldots+1$

即证：$\frac{t}{n}(n-1)^t \le t(n-1)^{t-1}+\ldots+1$

易知上式对任意 $n\ge1$都成立，得证。

e) 证明：$E[X_t] \le n/(t+1)$

由上面证明可知 $E[X_t]\le \sum_{r=1}^n(1-r/n)^t$，故有：

$E[X_t] \le \sum_{r=1}^n(1-r/n)^t $
$=\frac{1}{n^t}\sum_{r=1}^n(n-r)^t $
$=\frac{1}{n^t}\sum_{r=1}^{n-1} $
$\le\frac{n}{t+1}$