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.

這節(jié)列出一些你需要記住的一些基本的公式或者能夠推倒出來并且復習一些證明技巧

1.2.1 Exponents(指數(shù))


image.png

1.2.2 Logarithms(對數(shù))
In computer science,all logarithms are to the base 2 unless specified otherwise

在計算機科學中，所有的對數(shù)都是以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.5 The P Word

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi閱讀 7,847評論 0贊 10
  • 無論如何不要重復你的意思，不要用哲學式的循環(huán)疊加論證習慣，因為hr根本沒心情聽你講那么多，除了第一句中心觀點其他都...
    SeniaCheng閱讀 851評論 0贊 0
  • 一、引言 數(shù)據(jù)的序列化在Android開發(fā)中占據(jù)著重要的地位，無論是在進程間通信、本地數(shù)據(jù)存儲又或者是網(wǎng)絡數(shù)據(jù)傳輸...
    CQ_TYL閱讀 1,043評論 0贊 0
  • 原則：從身邊的頭部做起。 不要想太遠，從身邊頭部開始。如果你在一個小團隊里，那么就先占領(lǐng)團隊的頭部；如果你是...
    D051飛鷹閱讀 280評論 0贊 0
  • 今天一整天都和學妹在一起。聊聊過往，說說近況，偶爾抒發(fā)下心情，一天就這么打發(fā)了。合影發(fā)在朋友圈表示好心情。到家，媽...
    微00閱讀 168評論 2贊 2

友情鏈接更多精彩內(nèi)容