数学知识复习
记得高中的时候数学能力还是很突出的，但到了大学，高数好像离十里越来越远。过去这么长时间，已经有了定论：十里的数学知识已还给老师！这还真是让人崩溃，现在无处不数学，当然为了研究算法也得把高数给拾回来，所以有了本篇数学知识的复习。
此篇应该会一直补充，十里会边学习边丰富文章内容，一方面根据需求复习数学的基础知识，另一方面锻炼整理能力。
虽然部分知识很简单，也在这里一并整理上，主要参考：《数据结构与算法分析——C语言描述》
指数
$$ \begin{aligned} & X^AX^B=X^{A+B}\newline & \frac{X^A}{X^B}=X^{A-B}\newline & (X^A)^B=X^{AB}\newline & X^N+X^N=2X^N \ne X^{2N}\newline & 2^N+2^N=2^{N+1} \end{aligned} $$
对数
除了特殊说明，所有的对数均以2为底数。
$$ \begin{aligned} & \log_AB=\frac{\log_CB}{\log_CA}\newline & \log AB=\log A + \log B\newline & \log\frac{A}{B}=\log A - \log B\newline & \log (A^B)=B\log A\newline & \log X < X(对所有的X>0成立。) \end{aligned} $$
级数
几何级数
公式
$$\begin{equation} \sum_{i=0}^N A^i=\frac{A^{N+1}-1}{A-1} \end{equation}\label{eq1}$$
分两种情况讨论：
-
$A = 1$
此时，有：
$$\begin{equation} \sum_{i=0}^N A^i\xrightarrow[]{A=1}\sum_{i=0}^N 1=N \end{equation}\label{eq4}$$
-
$A \ne 1$
公式 $\ref{eq1}$ 证明：
$$ S=1+A+A^2+A^3+A^4+\dots+A^N $$
$AS=A\times S+1-1$, 有:
$$ \begin{aligned} & AS=1+A+A^2+A^3+A^4+\dots+A^N+A^{N+1}-1\newline & \therefore (A-1)S=AS-S=A^{N+1}-1\newline & \therefore S=\frac{A^{N+1}-1}{A-1} \end{aligned} $$
那么可得：
$$ \sum_{i=0}^N A^i=\frac{A^{N+1}-1}{A-1} $$
特别的，当 $A=2$ 时，有:
$$ \sum_{i=0}^N 2^i=2^{N+1}-1 $$
另外当 $0<A<1$ 时，由 $\ref{eq1}$ 公式还可以得到公式 $\ref{eq2}$:
$$\begin{equation} \sum_{i=0}^N A^i \le \frac{1}{1-A} \end{equation}\label{eq2}$$
公式 $\ref{eq2}$ 表示了 $N\rightarrow\infty$ 值趋近于 $\frac{1}{1-A}$ 简单证明过程如下：
$$ \begin{aligned} & S = 1 + A + A^2 + A^3 + A^4 + \dots \newline & AS = A + A^2 + A^3 + A^4 + \dots \newline & \because 0<A<1 \newline & \therefore S-AS \le 1 \newline & \therefore \sum_{i=0}^N A^i = S \le \frac{1}{1-A} \end{aligned} $$
算术级数
另一种常用类型的级数是算术级数，任何如下公式 $\ref{eq3}$ 的级数都可以通过基本公式计算值。
$$\begin{equation} \sum_{i=1}^N i=\frac{N(N+1)}{2} \approx \frac{N^2}{2} \end{equation}\label{eq3}$$
比如，$1+5+9+13+\dots+(4N-3)$ 有：
$$\begin{equation} \sum_{i=1}{^N} 4N-3=N(2N-1) \end{equation}\label{eq5}$$
公式 $\ref{eq5}$ 计算过程依赖于公式 $\ref{eq4}$ 和 $\ref{eq3}$:
$$ \begin{aligned} \sum_{i=1}{^N} 4N-3&=1+5+9+13+\dots+(4N-3) \newline &=4(1+2+3+\dots+N)-3(1+1+1+\dots+1) \newline &=\frac{4N(N+1)}{2}-3N \newline &=N(2N-1) \end{aligned} $$
平方和公式
不太常见的还有平方和公式，又叫四角锥数或金字塔数，如公式 $\ref{eq6}$：
$$\begin{equation} \sum_{i=1}^N i^2=\frac{N(N+1)(2N+1)}{6} \end{equation}\label{eq6}$$
这里简单说一下恒等式方法证明公式 $\ref{eq6}$ 的过程：
已知 $(N+1)^3=N^3+3N^2+3N+1$，那么可得：
$$ \begin{aligned} (N+1)^3-N^3&=3N^2+3N+1 \newline N^3-(N-1)^3&=3(N-1)^2+3(N-1)+1 \newline (N-1)^3-(N-2)^3&=3(N-2)^2+3(N-2)+1 \newline &\ \vdots \newline 2^3-1^3&=3\times 1^2+3\times 1 + 1 \end{aligned} $$
恒等式左右相加可得:
$$ \begin{aligned} (n+1)^3-1&=3(1^2+2^2+3^2+\dots+N^2)+3(1+2+3+\dots+N)+N \newline &\downarrow \newline 1^2+2^2+3^2+\dots+N^2i&=\frac{(N+1)^3-\frac{3N(N+1)}{2}-N-1}{3} \end{aligned} $$
最终整理可得:
$$ \sum_{i+1}^N i^2=1+2^2+3^2+\dots+N^2=\frac{N(N+1)(2N+1)}{6} $$
其它证明方法可参考:平方和公式
冯哈伯公式(Faulhaber’s formula)
平方和公式是冯哈伯公式(Faulhaber’s formula2)的一个特例，可知有如下有近似估计公式:
$$ \sum_{i=1}^N i^k \approx \frac{N^{k+1}}{\vert k+1 \vert},\ k\ne-1 $$
可以看到上述公式的条件为 $k\ne-1$，$k=-1$ 时公式 $\ref{eq6}$ 是不成立的，这时需要用到一个据说在计算机领域经常用到的公式：
$$ H_N=\sum_{i=1}^N \frac{1}{i} \approx \log_eN $$
$H_N$ 叫做调和数，上述近似式的误差趋近于 $\gamma\approx 0.57721566$，这个数值称为欧拉常数(Euler’s constant)
代数运算
$$ \begin{aligned} & \sum_{i=1}^N f(N)=Nf(N)\newline & \sum_{i=n_{0}}^N f(i)=\sum_{i=1}^N f(i) - \sum_{i=1}^{n_{0}-1} f(i) \end{aligned} $$
证明方法
数据结构及算法分析中针对结论常用的的证明方法有归纳法和反证法。
归纳法
归纳法有两个标准的部分：
- 证明基准情形：确定定理对于某些值的正确性；
- 归纳假设
以公式 $\ref{eq6}$ 为例进行说明，归纳法证明如下。
对于基准情形，定理当 $N=1$ 时代入数可知成立；对于归纳假设，假设公式 $\ref{eq6}$ 对于 $1 \le k \le N$ 成立，在此情况下，只需证明 $N+1$ 时公式同样成立即可。
如果 $N\ge1$, 易得：
$$ \sum_{i=1}^{N+1} i^2=\sum_{i=1}^{N} i^2 + (N+1)^2 $$
代入公式 $\ref{eq6}$:
$$ \begin{aligned} \sum_{i=1}^{N+1} i^2&=\frac{N(N+1)(2N+1)}{6}+(N+1)^2 \newline &=\frac{(N+1)(N+2)(2N+3)}{6} \newline &=\frac{(N+1)[(N+1)+1][2(N+1)+1]}{6} \end{aligned} $$
可以看到, $N+1$ 时符合，定理得证。
反证法
通过证明定理不成立，然后证明该假设导致某个已知的性质不成立，从而说明愿假设是错误的。