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.5 The P Word

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,839评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,543评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,116评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,371评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,384评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,111评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,416评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,053评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,558评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,756评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,324评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2 345

推荐阅读更多精彩内容

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,294评论 0 10
  • 无论如何不要重复你的意思,不要用哲学式的循环叠加论证习惯,因为hr根本没心情听你讲那么多,除了第一句中心观点其他都...
    SeniaCheng阅读 815评论 0 0
  • 一、引言 数据的序列化在Android开发中占据着重要的地位,无论是在进程间通信、本地数据存储又或者是网络数据传输...
    CQ_TYL阅读 912评论 0 0
  • 原则:从身边的头部做起。 不要想太远,从身边头部开始。如果你在一个小团队里,那么就先占领团队的头部;如果你是...
    D051飞鹰阅读 219评论 0 0
  • 今天一整天都和学妹在一起。聊聊过往,说说近况,偶尔抒发下心情,一天就这么打发了。合影发在朋友圈表示好心情。到家,妈...
    微00阅读 151评论 2 2