1.2 Mathematics Reviews

This section lists some of the basic formulas you need to memorize or be able to derive and reviews basic proof techniques.

这节列出一些你需要记住的一些基本的公式或者能够推倒出来并且复习一些证明技巧

1.2.1 Exponents(指数)

image.png

1.2.2 Logarithms(对数)
In computer science,all logarithms are to the base 2 unless specified otherwise

在计算机科学中，所有的对数都是以2为底的，除非另外指定

Definition 1.1

$X^{A}=B$ if and only if $log_X{B}=A$
Several convenient equalities follow from this definition.

Theorem 1.1

$log_A{B}=\frac{log_C{B}}{log_C{A}};A,B,C>0,A≠1$

Proff

Let X= $log_C{B}$ ,Y= $log_C{A}$ and Z= $log_A{B}$ .Then by definition of logarithms , $C^X=B$ , $C^Y=A$ ,and $A^Z=B$ .Combining these three equalities yields $C^X=B=(C^Y)^Z$ .Therefore ,X=YZ,which implies Z=X/Y,proving the theorem

Theorem1.2

$log{AB}=log{A}+log{B};A,B>0$

Proff

Let X= $log{A}$ ,Y= $log{B}$ ,and Z= $log{AB}$ .Then,assuming the default base of 2, $2^X=A,2^Y=B,$ and $2^Z=AB$ .Combining the last thress equalities yields $2^X2^Y=AB=2^Z$ .Therefore X+Y=Z,which proves the theorem.
Some other useful formulas,which can all be derived in a similar manner,follow.
$log{A/B}=log{A}-log{B}$
$log({A^B})=Blog{A}$
$log{X}<X$ for all X>0

$log{1}=0,log{2}=1,log{1024}=10,log{1048576}=20$

1.2.3 Series

The easiest formulas to remember are
$\sum_{i=1}^{N} {2^{N+1}}-1$
and the companion,
$\sum_{i=0}^{N}{\frac{A^{N+1}-1}{A-1}}$
In the later formula,if 0<A<1,then
$\sum_{i=0}^{N}{A^i}≤\frac{1}{1-A}$
and as N tends to $\infty$ ,the sum approaches $\frac{1}{1-A}$ .These are the 'geometric series' formulas.

We can derive the last formula for $\sum_{i=0}^{N}{A^i}(0<A<1)$ in the following manner.Let S be the sum.Then
$S=1+A+A^2+A^3+A^4+A^5+...$
Then
$AS=A+A^2+A^3+A^4+A^5+...$
If we subtract these two equations (which is permissible only for a convergent series)
virtually all the terms on the right side cancel,leaving
$S-AS=1$
which implies that
$S=\frac{1}{1-A}$
we can use the same technique to compute $\sum_{i=1}^{\infty}{\frac{i}{2^i}}$ ,a sum that occurs frequently.We write
$S=\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\frac{4}{2^4}+\frac{5}{2^5}+...$
and multiply by 2,obtaining
$2S=1+\frac{2}{2}+\frac{3}{2^2}+\frac{4}{2^3}+\frac{5}{2^4}+\frac{6}{2^5}+...$
Substracting these two equations yields
$S=1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+\frac{1}{2^5}+...$
Thus S=2
Another type of common series in analysis is the arithmetic series.Any such series can be evaluated from the basic formula.
$\sum_{i=1}^{N}{i}=\frac{N(N+1)}{2}≈N^2/2$

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 the next to last terms(total 3k+1),and so on.Since there are k/2 of these paris,the total sum is k(3k+1)/2,which is the same answer as before.
The next two formulas pop up now and then but are fairly uncommon.
$\sum_{i=1}^{N}{i^2}=\frac{N(N+1)(2N+1)}{6}≈\frac{N^3}{3}$
$\sum_{i=1}^{N}{i^k}≈\frac{N^(k+1)}{|k+1|},k≠-1$
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 number $H_N$ are known as the harmonic numbers,and the sum is known as a harmonic sum.The error in the following approximation tends to $\gamma≈0.57721566$ ,which is known as Euler's Constant.
$H_N=\sum_{i=1}^{N}{\frac{1}{i}}≈log_{e}{N}$
These two formulas are just general algebraic manipulations.
$\sum_{i=1}^{N}{f(N)}=Nf(N)$
$\sum_{i=n_0}^{N}{f(i)}=\sum_{i=1}^{N}{f(i)-\sum_{i=1}^{n_0-1}{f(i)}}$

1.2.4 Modular Arithmetic
We say that A is congruent to B modulo N,written $A\equiv B(mod \space N)$ ,if N divides A-B.Intuitively,this means that the remainder is the same when either A or B is divided by N,Thus , $81\equiv61\equiv1(mod\space10)$ ,As with equality, if $A\equiv B(mod\space N)$ ,then $A+C\equiv B+C(mod\space N)$ and $AD\equiv BD(mod\space N)$ .

Often,N is a prime number.In that case,there are three important theorems.
First ,if N is prime,then $ab\equiv 0(mod\space N)$ is true if and only if $a\equiv0(mod\space N)$ or $b\equiv0(mod\space N)$ .In other words,if a prime number N divides a product of two numbers.it divides at least one of the two numbers.

Second,if N is prime,then the equation $ax\equiv1(mod\space N)$ has a unique solution(mod N),for all 0<a<N,This solution 0<x<N,is the multiplicative inverse.

Third,if N is prime,then the equation $x^2\equiv a (mod\space N)$ has either two solutions(mod N),for all 0<a<N,or no solutions.

There are many theorems that apply to modular arithmetic ,and some of them require extraordinary proofs in number theory.We will use modular arithmetic sparingly,and the preceding theorems will suffice.

1.2 Mathematics Reviews