1.2. Mathematics Review
1.2.数学复习
This section lists some of the basic formulas you need to memorize or beable to derive and reviews basic proof techniques.
这一部分列出了一些你需要记住的或者是导出的基础数学公式并且复习基础的证明方法。
1.2.1. Exponents
1.2.1指数
1.2.2.Logarithms
1.2.2.对数
In computer science, all logarithms are to base 2 unless specified otherwise.
在计算机科学中，所有的对数都是以2为底数的除非有特殊声明。
DEFINITION: 
if and only if 
定义：当且仅当
Several convenient equalities follow from this definition.
通过这个定义可以推导出几个便利的公式
THEOREM 1.1.
定理1.1.
PROOF:
证明：
Let 
, and
. Then, by the definition of logarithms
, and 
. Combining these three equalities yields
. Therefore, x = yz, which implies z =x/y, proving the theorem.
令, 和。那么，通过给出的对数的定义, and 。结合这三个等式可以推导出。因此，x = yz，那么z = x/y，定理由此可证。
THEOREM 1.2.
定理1.2.
log ab = log a + log b
PROOF:
证明：
Let x = log a, y = log b, z = log ab. Then,assuming the default base of 2, 
. Combining the last three equalities yields
. Therefore, x + y= z, which proves the theorem.
令x = log a, y = log b, z = log ab。默认底数为2，。结合后边这三个等式，则x + y = z，由此定理可证。
Some other useful formulas, which can all be derived in a similar manner, follow.
下面这些有用的公式，都可以用相似的方法推导。
1.2.3.Series
1.2.3.级数
The easiest formulas to remember are
and the companion,
要记住的最简单的公式是类似的
。
In the latter formula, if 0 < a < 1, then
and as n tends to
, the sum approaches 1/(1 -a). These are the"geometric series" formulas.We can derive the last formula for 
in the following manner. Let S be the sum.Then
Then
接下来，如果0 < a < 1,那么
，并且当n趋向于时，结果无限接近1/(1 -a)。这些是“等比级数”公式。我们就可以用下面的方法导出最后的公式。把这个总和记为S，那么，那么
If we subtract these two equations (which is permissible only for a convergent series), virtually all the terms on the right side cancel, leaving
which simplies that 
We can use this same technique to compute
, a sum that occurs frequently. We write and multiply by 2, obtaining
。Subtracting these two equations yields。Thus, S = 2.
如果这两个等式相减（只允许是收敛级数时），右边所有项几乎都消去了，剩下了,就简化成了我们可以使用相同的方法计算多项式的和，我们写成，等式乘以二可得
，等式两边相减得到
，可得S = 2。
Another type of common series in analysis is the arithmetic series. Any such series can be evaluated from the basic formula.
在分析里边另外一个常见级数类型是算法级数。任一个这样的级数都能用基础的公式计算。
For instance, to find the sum 2 + 5 + 8 +. . . + (3k - 1), rewrite it as 3(1 + 2+ 3 +. . . + k) - (1+ 1 + 1 +. . . + 1), which is clearly 3k(k + 1)/2 - k. Another way to remember this is to add the first and last terms (total 3k + 1), the second and next to last terms (total 3k + 1), and so on. Since there are k/2 of these pairs, the total sum is k(3k + 1)/2, which is the same answer as before.
例如，为了计算2 + 5 + 8 +. . . + (3k - 1)的和，把它改写成3(1 + 2+3 +. . . + k) - (1 + 1 + 1 +. . . + 1)，就等于3k(k + 1)/2 -k。另外一个记住这个的方法就是首尾相加（和为3k + 1），第二项和倒数第二项相加（和为3k + 1），等等。有这样k/2对，总和就是k(3k + 1)/2，跟之前的答案相同。
The next two formulas pop up now and then but are fairly infrequent.
When k = -1, the latter formula is not valid. We then need the following formula, which is used far more in computer science than in other mathematical disciplines. The numbers, HN,are known as the harmonic numbers, and the sum is known as a harmonic sum. The error in the following aproximation tends to y
0.57721566,which is known as Euler's constant.
下面两个几乎用不到的公式我们也列举出来：
当k=-1时，后边这个公式没有意义。我们需要后边这个公式，它在计算机科学中比在其他数学科目中用得多得多。这个数列被称为调和数列，这个和被称为调和级数之和。下边这个近似值的误差趋近于y 0.57721566，这被称作欧拉常量。
These two formulas are just general algebraic manipulations.
下边这两个公式就是常见的代数运算：