Theoretical Computer Science Cheat Sheet

Denitions Series
f (n) = O(g(n)) i 9 positive c; n such that X
n X
n X
n
i = n(n2+ 1) ; i = n(n + 1)(2 n + 1) ; i = n (n4+ 1) :
0

0  f (n)  cg(n) 8n  n .
2 2
2 3
0

i i 6 i
f (n) =
(g(n)) i 9 positive c; n such that =1

In general:
=1 =1

f (n)  cg(n)  0 8n  n .
0

X
n  X n ,

i = m 1+ 1 (n + 1)m , 1 ,
0

m (i + 1)m , im , (m + 1)im
f (n) = (g(n)) i f (n) = O(g(n)) and +1 +1 +1

f (n) =
(g(n)). i
=1
 
i =1

nX , Xm m + 1 B nm ,k :
im = m 1+ 1
1

f (n) = o(g(n)) i limn!1 f (n)=g(n) = 0. k +1

i k k
!1 an = a
nlim i 8 > 0, 9n such that =1

Geometric series:
=0

jan , aj < , 8n  n .
0

X n X
1 X1
ci = c c ,,1 1 ; c 6= 1;
n
ci = 1 ,1 c ; ci = 1 ,c c ; jcj < 1;
0
+1

sup S least b 2 R such that b  s,

8s 2 S . i i i
X X
=0 =0 =1
n n n 1
inf S greatest b 2 R such that b  ici = nc ,((cn,+1)1)c + c ; c 6= 1; ici = (1 ,c c) ; jcj < 1:
+2 +1

s, 8s 2 S . i
=0 i
2
=0
2

lim inf a lim inf fai j i  n; i 2 Ng. Harmonic series:

n!1 n Xn X
n
iHi = n(n2+ 1) Hn , n(n4, 1) :
n!1
Hn = 1i ;
lim sup an lim supfai j i  n; i 2 Ng. i i
n i   
n!1 n!1
,n
X X
=1 =1
n n+1
k Combinations: Size k sub- Hi = (n + 1)Hn , n; m Hi = m + 1 Hn , m 1+ 1 :
sets of a size n set.
+1

i i
n Stirling numbers (1st kind): 
=1 =1

n n
X   
k
Arrangements of an n ele- 1. nk = (n ,nk! )!k! ; 2. n
k =2 ; 3. nk = n ,n k ;
ment set into k cycles.    k     
4. nk = nk nk ,, 11 ; 5. nk = n ,k 1 + nk ,, 11 ;
=0

n Stirling numbers (2nd kind):

k
Partitions of an n element  n m n n , k  n r + k  r + n + 1
X
set into k non-empty sets. 6. m k = k m , k ; 7. k = n ;

n n k  n + 1
k     
1st order Eulerian numbers: X X n r
=0

k
8. 9. s = r+s ;
Permutations   : : : n on m = m+1 ; k n,k
 n   n n
1 2

f1; 2; : : :; ng with k ascents.  k   k

n 10. nk = (,1)k k , nk , 1 ;
=0 =0

k 2nd order Eulerian numbers. 11. 1 = n = 1;

Cn Catalan Numbers: Binary n n n , 1 n , 1
trees with n + 1 vertices. 2 12. = 2n, , 1;
13. k = k k + k , 1 ; 1

n n n n n

14. = (n , 1)!; 15. = (n , 1)!Hn, ; 16. n = 1; 17. k  k ;
 n1   n , 1   n , 1  2  n   n  n
1

X 
n n  1
2n
18. = (n , 1) + k , 1 ; 19. n , 1 = n , 1 = 2 ; 20. = n!; 21. Cn = n + 1 n ;
kn   n  k n  n   n k k  n , 1  n , 1 =0

22. = = 1; 23. k = n , 1 , k ; 24. k = (k + 1) k + (n , k) k , 1 ;

 00  n n , 1 n n n + 1
25. 1 if k = 0, n
26. 1 = 2 , n , 1; n n
27. 2 = 3 , (n + 1)2 + 2 ;
k = 0 otherwise
X n  n x + k  n X m n + 1 n X n  n  k 
28. n
x = k n ; 29. m = k (m + 1 , k)n (,1)k ; 30. m! m = k n,m ;
n X
k
n  n n , k 
=0 k =0
 n   n 
k =0

31. m = k m (,1)n,k,m k!; 32. 0 = 1; 33. n = 0 for n 6= 0;

 n  k  n , 1 
=0
 n , 1  n  n  (2n)n
X
34. k = (k + 1) k + (2n , 1 , k) k , 1 ; 35. k = 2n ;
  X n  n x + n , 1 , k  n + 1  X n k  Xn k
k =0

36. x ,x n = k 2n ; 37. m+1= = (m + 1)n,k ; k m m

k =0 k k =0
 Theoretical Computer Science Cheat Sheet
Identities Cont. Trees
 n + 1  X  n  k  X
n k Xn 1k  x  X n  n x + k  Every tree with n
38. m + 1 = n , k 39. x , n =
k m = k m n = n! k k! m ; k 2n ; vertices has n , 1
 n  X n k + 1 
k =0 =0
  X  n + 1  k 
k =0
edges.
40. m = k m+1 (,1)n,k ; 41. mn = k + 1 m (,1)m,k ; Kraft inequal-
 m + n +k1  Xm n + k  m + n + 1k X m n + k ity: If the depths
42. = k k ; 43. = k(n + k) ; of the leaves of
m
 n  X  n +k 1  k  =0
 n  X  n +m1  k  k k =0
a binary tree are
d ; :n: : ; dn :
44. m = (,1)m,k ; 45. (n , m)! m = (,1)m,k ; for n  m, X ,di
1

k + 1 m k + 1 m 2  1;
 n k X m , nm + n m + k   n k  X m , nm + n m + k  i
46. n , m = m+k n+k k ; 47. n , m = m + k n + k k ; =1

   X  k  n , k n
k  n k` + m X  k  n , k n and equality holds
48. ` +n m ` +` m = ` m k ; 49. ` + m ` = only if every in-
` m k : ternal node has 2
k k sons.
Recurrences
Master method: ,
1 T (n) , 3T (n=2) = n

Generating functions:
T (n) = aT (n=b) + f (n); a  1; b > 1 ,
1. Multiply both sides of the equa-
3 T (n=2) , 3T (n=4) = n=2 tion by xi .
If 9 > 0 such that f (n) = O(n b a, ) log

2. Sum both sides over all i for

then .. .. ..
. . . which the equation is valid.
T (n) = (n b a ): log

n , ,T (2) , 3T (1) = 2
3. Choose a generatingPfunction

3 2
log 1

If f (n) = (n b a ) then

log
G(x). Usually G(x) = 1 i
i x gi .
T (n) = (n b a log n):
log Let m = log n. Summing the left side 3. Rewrite the equation in terms of
=0

we get T (n) , 3m T (1) = T (n) , 3m =

2
2

If 9 > 0 such that f (n) =

(n b a  ), the generating function G(x).
log +
T (n) , nk where k = log 3  1:58496. 4. Solve for G(x).
and 9c < 1 such that af (n=b)  cf (n)
2

Summing the right side we get 5. The coecient of xi in G(x) is gi .

for large n, then mX
, n 3i = n mX
, ,

i Example:
1 1

T (n) = (f (n)): 2i : 3

i i
2
gi = 2gi + 1; g = 0:
+1 0

Substitution (example): Consider the

=0 =0

following recurrence Let c = . Then we have Multiply

X andi sum: X X
 
3

mX
, gi x = 2gixi + xi :
2

Ti = 2 i
Ti ; T = 2:
+1
2 2
1
n ci = n cc ,,11
1 m
i
+1

i i
P
0 0 0

Note that Ti is always a power of two. i =0

We choose G(x) = i xi gi . Rewrite
Let ti = log Ti . Then we have = 2n(c 2 n , 1) log

in terms of G(x):
0

ti = 2i + 2ti ; t = 1:
2

+1 1
= 2n(c k, c n , 1) ( 1) log
G(x) , g X i
Let ui = ti =2i . Dividing both sides of x
0
= 2G(x) + x:
= 2nk , 2n; i
the previous equation by 2i we get +1
0

ti = 2i + ti : and so T (n) = 3nk , 2n. Full history re- Simplify:

G(x) = 2G(x) + 1 :
+1

2i+1
2i +1
2i currences can often be changed to limited
Substituting we nd history ones (example): Consider x 1,x
ui = + ui ; u = ; X
i, 1
Solve for G(x):
Ti = 1 + Tj ; T = 1:
1 1
+1 2 1 2
x
G(x) = (1 , x)(1 , 2x) :
0

which is simply ui = i=2. So we nd j =0

that Ti has the closed form Ti = 2i i,1 . 2

Note that Expand this 
Summing factors (example): Consider Xi 2 1

using partial fractions:
the following recurrence Ti = 1 +
+1 Tj : G(x) = x 1 , 2x , 1 , x
T (n) = 3T (n=2) + n; T (1) = 1: j =0
0 1
Subtracting we nd X X
Rewrite so that all terms involving T Xi X
i, = x @2 2i xi , xi A
are on the left side
1

Ti , Ti = 1 + Tj , 1 , Tj X ii i
T (n) , 3T (n=2) = n:
0 0
+1

j =0 j =0
= (2 i+1
, 1)x : +1

Now expand the recurrence, and choose = Ti : i 0

a factor which makes the left side \tele-

scope" And so Ti = 2Ti = 2i .
+1
+1
So gi = 2 , 1.
i
 Theoretical Computer Science Cheat Sheet
p p
  3:14159, e  2:71828,  0:57721, =  1:61803, 1+
2
5
^ = ,  ,:61803
1
2
5

i 2i pi General Probability
1 2 2 Bernoulli Numbers (Bi = 0, odd i 6= 1): Continuous distributions:Z If
b
2 4 3 B = 1, B = , , B = , B = , ,
0 1
1
2
1
4
1
Pr[a < X < b] = p(x) dx;
B = ,B =, ,B = .
2 6 30

3 8 5 1 1 5
a
then p is the probability density function of
6 42 8 30 10 66

4 16 7 Change of base, quadratic formula:

p X . If
5 32 11 log a
logb x = log b ;x , b  b , 4ac : 2
Pr[X < a] = P (a);
6 64 13 a 2 a then P is the distribution function of X . If
7 128 17 Euler's number e: P and p both existZthen
8 256 19 e = 1+ + + + +


1 1 1 1 a
 x n x
2 6 24 120
P (a) = p(x) dx:
9 512 23 lim 1+ n =e : ,1
n!1
10 1,024 29 ,1 +
n < e < ,1 +
n : +1
Expectation: If X is discrete
X
,1 +
n = e , e + 11e , O  1  :
1 1

11 2,048 31 n n E[g(X )] = g(x) Pr[X = x]:

12 4,096 37 1 x
n 2n 24n n If X continuous
13 8,192 41 Harmonic numbers:
2 3
Z 1 then Z1
14 16,384 43 E[g(X )] = g(x)p(x) dx = g(x) dP (x):
1, , , , , , ,
3 11 25 137 49 363 761
, 7129
;::: ,1 ,1
15 32,768 47 2 6 12 60 20 140 280 2520
Variance, standard deviation:
16 65,536 53 ln n < Hn < ln n + 1
; VAR[X ] = E[X ] , E[X ] ; 2 2

17 131,072 59 p
Hn = ln n + + O n1 :  = VAR[X ]:
18 262,144 61 For events A and B :
19 524,288 67 Factorial, Stirling's approximation: Pr[A _ B ] = Pr[A] + Pr[B ] , Pr[A ^ B ]
20 1,048,576 71 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, ::: Pr[A ^ B ] = Pr[A]
Pr[B ];
21 2,097,152 73 p  n n  1  i A and B are independent.
22 4,194,304 79 n! = 2n e 1+ n : A ^ B]
Pr[AjB ] = Pr[Pr[
23 8,388,608 83 Ackermann's B]
8 jfunction and inverse: For random variables X and Y :
24 16,777,216 89 <2 i=1
E[X
Y ] = E[X ]
E[Y ];
25 33,554,432 97 a(i; j ) = : a(i , 1; 2) j=1
26 67,108,864 101 a(i , 1; a(i; j , 1)) i; j  2 if X and Y are independent.
27 134,217,728 103 (i) = minfj j a(j; j )  ig: E [ X + Y ] = E[X ] + E[Y ];
28 268,435,456 107 Binomial distribution: E[cX ] = c E[X ]:
 Bayes' theorem:
29 536,870,912 109 Pr[X = k] = nk pk qn,k ; q = 1 , p; B jAi ] Pr[Ai ] :
30 1,073,741,824 113 Pr[Ai jB ] = PnPr[Pr[
n n
X A ] Pr[B jA ]
j j j
31 2,147,483,648 127 E[X ] = k k pk qn,k = np:
=1

Inclusion-exclusion:
32 4,294,967,296 131 k =1 h _n i X n
Pascal's Triangle Poisson distribution: Pr Xi = Pr[Xi ] +
, k
Pr[X = k] = e k! ; E[X ] = :
i i
1 h ^k i
=1 =1

X
n X
11 Normal (Gaussian) distribution: (,1)k +1
Pr Xij :
121 k ii <


<ik j
p(x) = p 1 e, x, 2 = 2 ; E[X ] = :
=2 =1

1331 2
( ) 2
Moment inequalities:
The \coupon collector": We are given a
 
Pr jX j   E[X ]  1 ;
14641
1 5 10 10 5 1 random coupon each day, and there are n h  i
dierent types of coupons. The distribu- Pr X , E[X ]  
  1 :
1 6 15 20 15 6 1 tion of coupons is uniform. The expected
2

1 7 21 35 35 21 7 1 number of days to pass before we to col- Geometric distribution:

1 8 28 56 70 56 28 8 1 lect all n types is Pr[X = k] = pqk, ; q = 1 , p; 1

nHn : X1 1
1 9 36 84 126 126 84 36 9 1 E[X ] = kpqk, = p : 1

1 10 45 120 210 252 210 120 45 10 1 k =1

 Theoretical Computer Science Cheat Sheet
Trigonometry Matrices More Trig.
Multiplication: C
X
n
(0,1)
C = A
B; ci;j = ai;k bk;j : b h a
b (cos ; sin ) k
C 
=1

A Determinants: det A 6= 0 i A is non-singular.

A c B
det A
B = det A
det B;
(-1,0) (1,0)
Law of cosines:
c a X Yn
B (0,-1)
det A = sign()ai; i : c = a +b ,2ab cos C:
2 2 2

Pythagorean theorem:  i =1
( )
Area:
C =A 2 2
+B : 2 2  2 and 3  3 determinant:
 a b  A = hc;
 c d  = ad , bc;
1
2

Denitions: = ab sin C;
1

sin a = A=C; cos a = B=C;  a b c       

2

 d e f  = g  b c  , h  a c  + i  a b  = c sin A sin B
2

csc a = C=A; sec a = C=B;

 g h i   e f   d f  d e 2 sin C :
sin a = A ;
tan a = cos cot a = cos a = B: Heron's formula:
a B sin a A aei + bfg + cdh
Area, radius of inscribed circle: = , ceg , fha , ibd: A = ps
sa
sb
sc ;
AB; A +AB
B +C:
Permanents: s = (a + b + c);
1
1

XY
n
2

sa = s , a;
2

Identities: perm A = ai; i :

 i
( )
sb = s , b;
sin x = csc1 x ; cos x = sec1 x ;
=1

Hyperbolic Functions sc = s , c:
tan x = cot1 x ; sin x + cos x = 1;
2 2 Denitions:
x ,x x ,x
More identities:
r
sinh x = e ,2e ; cosh x = e + e ; sin = 1 , 2cos x ;
x
1 + tan x = sec x;
2 2
1 + cot x = csc x;
2 2
x e,x 2 2

r
,

sin x = cos  , x ; tanh x = eex ,
+ e,x ;
1
csch x = sinh x ; 1 + cos x ;
sin x = sin( , x); cos x =
,
1 ; 1 : r 1 , 2cos x
2 2

sech x = cosh coth x = tanh

cos x = , cos( , x); tan x = cot  , x ; 2
x x tan x = 1 + cos x ;
cot x = , cot( , x); csc x = cot x , cot x; Identities: 2

cosh x , sinh x = 1;
2 2
tanh x + sech x = 1; 2 2 = 1 ,sincos x
x ;
sin(x  y) = sin x cos y  cos x sin y; x ;
coth x , csch x = 1;
2 2
sinh(,x) = , sinh x; = 1 +sincos
cos(x  y) = cos x cos y  sin x sin y;
cosh(,x) = cosh x; tanh(,x) = , tanh x; r 1 + cosx x
tan(x  y) = 1tan x  tan y cot x = 1 , cos x ;
 tan x tan y ; sinh(x + y) = sinh x cosh y + cosh x sinh y;
2

x;
cot(x  y) = cot x cot y  1 cosh(x + y) = cosh x cosh y + sinh x sinh y; = 1 +sincos
cot x  cot y ; sin
x
x ;
sin 2x = 2 sin x cos x; sin 2x = 2 tan x ; sinh 2x = 2 sinh x cosh x; = 1 , cos x
1 + tan x 2
ix , e,ix
cos 2x = cos x , sin x; cos 2x = 2 cos x , 1; cosh 2x = cosh x + sinh x;2 2

sin x = e
2i ;
2 2 2

cosh x + sinh x = ex; cosh x , sinh x = e,x;

cos 2x = 1 , 2 sin x; cos 2x = 1 , tan x ; ix
cos x = e +2e ;
,ix
2
2

1 + tan x 2

(cosh x + sinh x)n = cosh nx + sinh nx; n 2 Z;

2 tan x x , 1;
cot 2x = cot2 cot
ix , e,ix
tan x = ,i eeix +
2

tan 2x = ;
1 , tan x x 2 sinh x = cosh x , 1; 2 cosh x = cosh x + 1: e,ix ;
2 2
2
2 2

= ,i ee ix ,
sin(x + y) sin(x , y) = sin x , sin y; 2 2 ix 12

 sin  cos  tan  : : : in mathematics + 1;

2

cos(x + y) cos(x , y) = cos x , sin y: you don't under-

sin x = sinhi ix ;
2 2

0 0 p1 p0 stand things, you

Euler's equation: 
just get used to
1 3 3

eix = cos x + i sin x; ei = ,1: 

6
p 2
p
2 3
cos x = cosh ix;
2 2
1 them.
v2.0 c 1994 by Steve Seiden p p { J. von Neumann tan x = tanh ix :
4 2 2

 3 i
3 1

sseiden@acm.org 
3 2 2

http://www.mpi-sb.mpg.de/~seiden 2
1 0 1
 Theoretical Computer Science Cheat Sheet
Number Theory Graph Theory
The Chinese remainder theorem: There ex- Denitions: Notation:
ists a number C such that: Loop An edge connecting a ver- E (G) Edge set
tex to itself. V (G) Vertex set
C  r mod m
1 1
Directed Each edge has a direction. c(G) Number of components
.. .. .. Simple Graph with no loops or G[S ] Induced subgraph
. . . deg(v) Degree of v
multi-edges.
C  rn mod mn Walk A sequence v e v : : : e`v` .
(G) Maximum degree
(G) Minimum degree
0 1 1

if mi and mj are relatively prime for i 6= j . Trail A walk with distinct edges.
Euler's function: (x) is the number of Path A trail with distinct (G) Chromatic number
positive integersQ less than x relatively vertices. E (G) Edge chromatic number
prime to x. If ni pei i is the prime fac- Connected A graph where there exists Gc Complement graph
torization of x then
=1
a path between any two K n Complete graph
Yn vertices. K n1 ;n2 Complete bipartite graph
(x) = pei i , (pi , 1): 1

Component A maximal connected r( k; `) Ramsey number

i subgraph. Geometry
=1

Euler's theorem: If a and b are relatively Tree A connected acyclic graph.

prime then Free tree A tree with no root. Projective coordinates: triples
1  a b mod b:( )
DAG Directed acyclic graph. (x; y; z ), not all x, y and z zero.
Eulerian Graph with a trail visiting (x; y; z ) = (cx; cy; cz ) 8c 6= 0:
Fermat's theorem: Cartesian Projective
1  ap, mod p: 1 each edge exactly once.
Hamiltonian Graph with a cycle visiting (x; y) (x; y; 1)
The Euclidean algorithm: if a > b are in- each vertex exactly once. y = mx + b (m; ,1; b)
tegers then Cut A set of edges whose re- x=c (1; 0; ,c)
gcd(a; b) = gcd(a mod b; b): moval increases the num- Distance formula, Lp and L1
Q n
If i pei i is the prime factorization of x ber of components. metric:
Cut-set A minimal cut. p
(x , x ) + (y , y ) ;
=1
then
X Y
2 2
n ei
S (x) = d = pip ,,1 1 :
+1 Cut edge A size 1 cut. jx , x jp + jy , y jp =p ;
1 0 1 0

1
k-Connected A graph connected with
jx , x jp + jy , y jp  =p :
1 0 1 0
i
djx i=1
the removal of any k , 1 lim 1

Perfect Numbers: x is an even perfect num- vertices. p!1 1 0 1 0

ber i x = 2n, (2n , 1) and 2n , 1 is prime.

1 k-Tough 8S  V; S 6= ; we have Area of triangle (x ; y ), (x ; y ) 0 0 1 1

Wilson's theorem: n is a prime i k
c(G , S )  jS j. and (x ; y ): 


2 2

(n , 1)!  ,1 mod n: k-Regular A graph where all vertices x , x y

abs  x , x y , y  :
 1 , y 0 1 0

have degree k.
1
2

Mobius 8inversion: k-Factor A k-regular spanning

2

Angle formed by three points:

0 2 0

>
< 10 if i = 1.
subgraph.
(i) = > (,1)r ifif ii isis the
not square-free.
Matching A set of edges, no two of (x ; y )
: product of
r distinct primes. which are adjacent.
2 2

Clique A set of vertices, all of ` 2

If X which are adjacent. 

G(a) = F (d); Ind. set A set of vertices, none of (0 ; 0) ` (x ; y ) 1 1 1

dja
which are adjacent. cos  = (x ; y `)
`(x ; y ) :
1 1 2 2

then X a Vertex cover A set of vertices which 1 2

F (a) = (d)G d : cover all edges. Line through two points (x ; y ) 0 0

dja Planar graph A graph which can be em- and (x ;y ):

 x y 1 
1 1

Prime numbers: beded in the plane.

pn = n ln n + n ln ln n , n + n lnlnlnnn Plane graph An embedding of a planar  x y 1  = 0:
  graph. x y 1 0 0

X
1 1

+ O lnnn ; deg(v) = 2m:

Area of circle, volume of sphere:
v2V A = r ; V = r : 2 4 3

(n) = lnnn + (lnnn) + (ln2!nn)

3

If G is planar then n , m + f = 2, so If I have seen farther than others,

 n 
2 3

f  2n , 4; m  3n , 6: it is because I have stood on the

+ O (ln n) : 4 Any planar graph has a vertex with de- shoulders of giants.
gree  5. { Issac Newton
 Theoretical Computer Science Cheat Sheet
 Calculus
Wallis' identity: Derivatives:
 = 2
12

23

34

54

65

67





1. d(cu) = c du ; 2. d(u + v) = du + dv ; 3. d(uv) = u dv + v du ;
dx dx dx dx,
dx ,
dx dx dx
Brouncker's continued fraction expansion: n) v du , u dv cu )
 =1+ 1
2
2
4. dx = nun, dx ; 5. dx = dx v dx ; 6. dx = cecu du
d (u du 1
d ( u=v ) d ( e
dx ;
2+
2
4
52
3

u
2+ 2+72



7. d(dxc ) = (ln c)cu du 8. d(ln u) 1 du
2+

Gregrory's series: dx ; dx = u dx ;
9. d(sin u) du 10. d(cos u) du
 = 1, + , + ,



dx = cos u dx ; dx = , sin u dx ;
1 1 1 1
4 3 5 7 9

Newton's series:
=1+ 1 1
3 11. d(tan u) du
dx = sec u dx ;
2
12. d(cot u) du
dx = csc u dx ;
2

2 2
3
2 + 2
4
5
2 +

13. d(sec u) = tan u sec u du ; 14. d(csc u) = , cot u csc u du ;
6 3 5

Sharp's series: dx dx dx dx
  ,
 = p1 1 , 1 + 1 , 1 +


15. dx = p1 , u du
d (arcsin u ) 1
dx ;
d(arccos u )
16. dx = p1 , u dx ; 1 du
6
3 3
3 3
5 3
7
1 2 3 2 2

Euler's series: 17. d(arctan u) = 1 du ; 18. d(arccot u) = ,1 du ;

dx 1 , u dx 2
dx 1 , u dx 2

2 = 2 + 2 + 2 + 2 + 2 +



1 1 1 1 1

19. d(arcsec u) 1 du 20. d(arccsc u) ,1 du

dx = up1 , u dx ; dx = up1 , u dx ;
6 1 2 3 4 5

2 = 2 + 2 + 2 + 2 + 2 +



1 1 1 1 1 2 2
8 1 3 5 7 9

2 = 2 , 2 + 2 , 2 + 2 ,



12
1
1
1
2
1
3
1
4
1
5 21. d(sinh u) du
dx = cosh u dx ; 22. d(cosh u) du
dx = sinh u dx ;
Partial Fractions
Let N (x) and D(x) be polynomial func-
23. d(tanh
dx
u) = sech u du ;
dx
2
24. d(coth
dx
u) = , csch u du ;
dx
2

tions of x. We can break down

N (x)=D(x) using partial fraction expan- 25. d(sech u) du
dx = , sech u tanh u dx ; 26. d(csch u) du
dx = , csch u coth u dx ;
sion. First, if the degree of N is greater
than or equal to the degree of D, divide 27. d(arcsinh
dx
u) = p 1 du ;
1 + u dx
28. d(arccosh
dx
u) = p 1 du ;
u , 1 dx
N by D, obtaining 2 2

N (x) = Q(x) + N 0 (x) ;

D(x) D(x) 29. d(arctanh
dx
u) = 1 du ;
1 , u dx 2
30. d(arccoth
dx
u) = 1 du ;
u , 1 dx 2

where the degree of N 0 is less than that of 31. d(arcsech u) = p,1 du ; 32. d(arccsch u) = p,1 du :
D. Second, factor D(x). Use the follow- dx u 1 , u dx 2 dx juj 1 + u dx 2

ing rules: For a non-repeated factor: Integrals:

N (x) = A + N 0 (x) ; Z Z Z Z Z
(x , a)D(x) x , a D(x) 1. cu dx = c u dx; 2. (u + v) dx = u dx + v dx;
where  (x)  Z Z Z
A= N xn dx = n +1 1 xn ; n 6= ,1;
3. 4. 1 dx = ln x; 5. ex dx = ex;
D(x) : +1

x
x a =
Z dx Z dv Z
For a repeated factor:
mX 6. = arctan x; 7. u dx dx = uv , v du
dx dx;
Z 1+x
N (x) , Ak + N 0 (x) ; Z
1 2

=
(x , a)m D(x) k (x , a)m,k D(x) =0 8. sin x dx = , cos x; 9. cos x dx = sin x;
where    Z Z
dk N (x)
Ak = k1! dx : 10. tan x dx = , ln j cos xj; 11. cot x dx = ln j cos xj;
k D(x)
x a = Z Z
The reasonable man adapts himself to the 12. sec x dx = ln j sec x + tan xj; 13. csc x dx = ln j csc x + cot xj;
world; the unreasonable persists in trying Z p
to adapt the world to himself. Therefore 14. arcsin xa dx = arcsin xa + a , x ; a > 0; 2 2

all progress depends on the unreasonable.

{ George Bernard Shaw
 Theoretical Computer Science Cheat Sheet
Z Calculus Cont. Z
p
15. arccos xa dx = arccos xa , a , x ; a > 0; 2 2
16. arctan xa dx = x arctan xa , a ln(a + x ); a > 0; 2 2

Z Z
2

17. sin (ax)dx = a

2 1
,ax , sin(ax) cos(ax)
; 18. cos (ax)dx = a ax + sin(ax) cos(ax) ;
2 1
,

Z Z
2 2

19. sec x dx = tan x;

2
20. csc x dx = , cot x;
2

Z n, 1 Z sinn, x dx; Z n, Z
21. sinn x dx = , sin nx cos x + n , 22. n x dx = cos x sin x + n , 1 cosn, x dx;
1 1

n cos n n
2 2

Z n , x Z Z n , Z
23. tann x dx = tan n,
n , 1 , tan x dx; n 6= 1; 24. cotn x dx = , cotn , 1 x , cotn, x dx; n 6= 1;
1 1
2 2

Z n, x n , 2 Z
25. secn x dx = tan xnsec n,
, 1 + n , 1 sec x dx; n 6= 1;
1
2

Z cot x cscn, x n , 2 Z Z Z
26. n
csc x dx = , n , 1 n ,
+ n , 1 csc x dx; n 6= 1; 27. sinh x dx = cosh x; 28. cosh x dx = sinh x;
1
2

Z Z Z Z  
29. tanh x dx = ln j cosh xj; 30. coth x dx = ln j sinh xj; 31. sech x dx = arctan sinh x; 32. csch x dx = ln tanh x  ;
Z Z Z
2

33. sinh x dx = sinh(2x) , x;

2 1 1
34. cosh x dx = sinh(2x) + x;
2 1 1
35. sech x dx = tanh x;
2

Z Z
4 2 4 2

p
36. arcsinh xa dx = x arcsinh xa , x + a ; a > 0; 2 2
37. arctanh xa dx = x arctanh xa + a ln ja , x j; 2
2 2

8 p
Z < x arccosh xa , x + a ; 2 2
if arccosh xa > 0 and a > 0,
38. arccosh xa dx = : p
x arccosh xa + x + a ; 2 2
if arccosh xa < 0 and a > 0,
Z dx  p 
39. p
a +x
= ln x + a + x ; a > 0; 2 2

Z Zp
2 2

dx = arctan x ; a > 0; p
40. a +x a a
1
41. a , x dx = x a , x + a2 arcsin xa ; a > 0;
2 2 2 2

Z
2 2 2 2

p a4 arcsin x ;
42. (a , x ) = dx = x (5a , 2x ) a , x +
2 2 3 2 2 2 2 2 3
a a > 0;
Z Z dx  a + x  Z
8 8

43. p dx x
= arcsin a ; a > 0; 1 
44. a , x = 2a ln  a , x  ;  45. (a ,dxx ) = = a pax , x ;
a ,x
Zp Z dx
2 2 2 2 2 2 3 2 2 2 2

p 2  p   p 
46. a  x dx = a  x  ln x + a  x  ;
2 x 2 a 2 2
47. px , a = ln x + x , a  ; a > 0;
2 2 2 2

Z dx  x  Z p
2 2 2 2

1
48. ax + bx = a ln  a + bx  ; 49. x a + bx dx = 2(3bx , 215 a)(a + bx) = ; 3 2

Z pa + bx Z 1 Z x  pa + bx , pab 
2 2

p 1
50. x dx = 2 a + bx + a p
x a + bx
dx; 51. pa + bx dx = p2 ln  pa + bx + pa  ; a > 0;
Z pa , x p 
 a + pa , x   Z p
52. , ,   53. x a , x dx = , (a , x ) = ;
2 2 2 2

x dx = a x a ln x
2
; 2 2 2 1 2 2 3 2

 p 
3

Z p p 4
Z dx  a + a , x  ;
54. x a , x dx = (2x , a ) a , x + arcsin a ; a > 0;
x a x 55. pa , x = , a ln 
2 2


2 2 2 2 2 2 2 1

x
Z x dx Z x dx
8 8 2 2

p p
56. pa , x = , a , x ; 57. pa , x = , x a , x + a2 arcsin a;x a > 0;
2
2 2 2 2

Z pa + x
2

p
2
 p  Z px , a p
2 2 2 2

58. dx = a + x , a ln 
2 2
 a + a + x 
; 59. dx = x , a , a arccos a ; a > 0;
2 2 2 2

  jxj
2 2 2 2

x x x
Z p Z dx
 
60. x x  a dx = (x  a
2 2 1 2
)=
2 3 2
; 61. p = a ln  px 1  ;
3
x x +a 2
a+ a +x2 2 2
 Theoretical Computer Science Cheat Sheet
Calculus Cont. Finite Calculus
Z Z p
=  xa x a ;
Dierence, shift operators:
62. p dx = a arccos jxaj ; a > 0; 63. p dx
2 2

f (x) = f (x + 1) , f (x);
1

x x ,a p x x a
Z Z
2 2 2 2 2 2

p x  a dx =  (x + a ) ; = E f (x) = f (x + 1):
64. p x dx = x  a ; 65.
2 2 2 2 3 2
2 2

x a 8  p x  3a x Fundamental Theorem: X
2 2 4 2 3

Z >
> 1  2 ax + b , b , 4ac  f ( x ) =
F ( x ) , f (x)x = F (x) + C:
< pb , 4ac ln  2ax + b + pb , 4ac  ; if b > 4ac,
2
2

66. dx X b X
b,
ax + bx + c = >
2 2
1
2
>
:p 2 2 ax + b f ( x ) x = f (i):
arctan p ; if b < 4ac, a i a
2

4ac , b 4ac , b 2 2 =

8 1   Dierences:
> p p
(cu) = c
u;
(u + v) =
u +
v;
Z dx < pa ln 2ax + b + 2 a ax + bx + c ; if a > 0, 2

67. p =
(uv) = u
v + E v
u;

ax + bx + c >
2 1 , 2ax
: p,a arcsin pb , 4ac ;, b if a < 0,
(xn ) = nxn, ; 1
2

Z p p Z
(Hx ) = x, ;
(2x) = 2x ; 1

68. ax + bx + c dx = 2 ax + b ax + bx + c + 4 ax , b p dx ;
(cx ) = (c , 1)cx;

,
,


x = x :
2

m,
2 2

4a 8a ax + bx + c
2 m 1

Sums:
Z Z p P cu x = c P u x;
69. p x dx = ax +a bx + c , 2ba p dx
2

; P(u + v) x = P u x + P v x;
ax + bx + c
2
ax + bx + c 2

8 ,1  2pcpax + bx + c + bx + 2c  P u
v x = uv , P E v
u x;

Z >
> p ln   ;
<
2

 if c > 0,
70. p dx =>
c x P xn x = xn+1 ; P x, x = H ;
x ax + bx + c > 1 m x 1

: p,c arcsin jxjpbxb+,2c4ac ; P cx x = cx ; P , x
x = , x
:

2 +1

if c < 0,
c, m m
Z
2

p
1 +1

Falling Factorial Powers:

71. x x + a dx = ( x , a )(x + a ) = ;
3 2 2 1 2 2 2 2 2 3 2
xn = x(x , 1)


(x , n + 1); n > 0;
Z Z
3 15

x = 1;
0

72. xn sin(ax) dx = , a xn cos(ax) + na xn, cos(ax) dx; 1 1

Z Z xn = (x + 1)

1
(x + jnj) ; n < 0;

73. xn cos(ax) dx = a xn sin(ax) , na xn, sin(ax) dx;1 1

xn m = xm (x , m)n :
+

Z n ax Z Rising Factorial Powers:

74. xn eax dx = x ae , na xn, eax dx; 1

xn = x(x + 1)


(x + n , 1); n > 0;

Z  ln(ax) 1

75. xn ln(ax) dx = xn x = 1;
n + 1 , (n + 1) ;
0
+1

Z Z xn = (x , 1)

1
(x , jnj) ; n < 0;

2

76. xn (ln ax)m dx = xn +1

(ln ax)m , m n m,
n + 1 x (ln ax) dx:
1

n+1 xn m = xm (x + m)n :
+

Conversion:
x 1
= x 1
= x 1 xn = (,1)n (,x)n = (x , n + 1)n
x
2
= x +x 2 1
= x ,x 2 1
= 1=(x + 1),n ;
x
3
= x + 3x + x 3 2 1
= x , 3x + x 3 2 1
xn = (,1)n (,x)n = (x + n , 1)n
x 4
= x + 6x + 7x + x 4 3 2 1
= x , 6x + 7x , x
4 3 2 1
= 1=(x , 1),n ;
x 5
= x + 15x + 25x + 10x + x
5 4 3 2 1
= x , 15x + 25x , 10x + x
5 4 3 2 1
X n n X n n
n
x = k
k
x = k (,1)n,k xk ;
x = x x = x k k
n n
1 1 1 1

X
=1 =1

x 2
= x +x 2 1
x 2
= x ,x 2 1
xn = (,1)n,k xk ;
x 3
= x + 3x + 2x 3 2 1
x 3
= x , 3x + 2x 3 2 1
k k
X n n
=1

x 4
= x + 6x + 11x + 6x 4 3 2 1
x 4
= x , 6x + 11x , 6x 4 3 2 1

x 5
= x + 10x + 35x + 50x + 24x
5 4 3 2 1
x 5
= x , 10x + 35x , 50x + 24x
5 4 3 2 1
xn = k xk :
k =1
 Theoretical Computer Science Cheat Sheet
Series
Taylor's series: Ordinary power series:
X 1 X
f (x) = f (a) + (x , a)f 0 (a) + (x ,2 a) f 00 (a) +


= (x ,i! a) f i (a):
2 i 1
( )
A(x) = ai xi :
i i
Expansions: =0
=0

1 X
1 Exponential power series:
1,x = 1 + x + x + x + x + 2



= xi ; 3 4
X
1 xi
i A(x) = ai i! :
X
1
=0

1 = 1 + cx + c x + c x +


= ci xi ;
i=0

1 , cx Dirichlet power series:

2 2 3 3

i X
1 a
X
1
=0

1 A(x) = i
1 , xn = 1 + xn + x n + x n +


2 3
= xni ;
i ix :
i =1

X
1 Binomial theorem: 
=0

x
(1 , x) = x + 2x + 3x + 4x +



2 3 4
= ixi ; X
n n
n,k k

2

 i (x + y )n = k x y:
X
1 =0

dn
xk dx 1 = x + 2nx + 3nx + 4n x +


= n i xi ;
k =0

n 1,x Dierence of like powers:

2 3 4

i nX
,
X
1 xi
=0
1

ex = 1+x + x + x +


xn , yn = (x , y) xn, ,k yk :

= i! ;
1 1
2 1 3

k
2 6
i
X
=0
1
=0
i For ordinary power series:
ln(1 + x) = x , x + x , x ,



1 2 1 3 1 4
= (,1)i xi ; +1
X
1
(ai + bi )xi ;
2 3 4
i A(x) + B (x) =
X1 xi
=1

ln 1 ,1 x = x + x + x + x +



1 2 1 3 1 4
= ; i
X
1
=0

i i
2 3 4

X1 =1
i xk A(x) = ai,k xi ;
= x , x + x , x +


= (,1)i (2xi + 1)! ;
2 +1

sin x 1 3 1 5 1 7

P i k =

A(x) , i ai xi = X
k , 1
3! 5! 7!
i
X
1

1 ai k xi ;
=0
i
= (,1)i (2xi)! ;
=0

= 1, x + x , x +


xk
2

cos x
+

1 i
1 2 1 4 1 6

X
2! 4! 6! =0

i
X1 A(cx) = i i c ai x ;
=0
i
tan, x = x , x + x , x +


= (,1)i (2xi + 1) ;
2 +1

i
1 1 3 1 5 1 7

X
3 5 7 =0

i   1
X1 n =0

(1 + x)n = 1 + nx + n n, x +


( 1) 2
= xi ; A0 (x) = (i + 1)ai xi ; +1
2
i  i i
1 i + n X
=0
1
,
X
=0

1 = 1 + (n + 1)x + n x +


+2
= xi ; xA0 (x) = iai xi ;
(1 , x)n
2
2
i i
Z
+1
i
X
=1

X1 1 a
=0

x i
ex , 1 =1, x+ x ,1
2
1
12
2
720
1
x +



4
= Bii!x ; A(x) dx = i, i
i x;
1

i
X1   i
A(x) + A(,x) = X
=1

1 (1 , p1 , 4x)
=0
1
2x = 1 + x + 2x + 5x +


2 3
= i +1 1 2ii xi ; a ix i; 2

i   2 i
2

X1 2i
=0

X
=0

p1 ,1 4x = 1 + x + 2x + 6x +


2 3
= i xi ; A(x) , A(,x) = ai x :
1
i
2 +1

 1 , p1 , 4x n i 
1 2i + n 2 2 +1

, n
x +


X i
P
=0

p 1
=0

= 1 + (2 + n)x + 4+ 2
= xi ; Summation: If bi = ij ai then
1 , 4x 2x 2
i i =0

X
1 B (x) = 1 ,1 x A(x):
=0

1 ln 1 = x + x + x + x +


=
3 11 25
Hi xi ;
1,x 1,x
2 3 4

Convolution: 0 1
2 6 12

  i
X
1 H xi
=1

1 ln 1 2

= x + x + x +


i, ; X
1 X
@
i
= aj bi,j A xi :
1

A(x)B (x) =
1 3 11

1,x
2 3 4

2 2 4 24
i i
X
1 i j
=2

x = x + x + 2x + 3x +


= Fi xi ;
=0 =0

1,x,x
2 3 4

God made the natural numbers;

2
i
X
1
=0

Fn x = Fn x + F n x + F n x +


= Fni xi : all the rest is the work of man.

1 , (Fn, + Fn )x , (,1)n x
2 3

1 +1
2
2 3

i
=0
{ Leopold Kronecker
 Theoretical Computer Science Cheat Sheet
Series Escher's Knot
Expansions:
X
1    1 ,n X1 i
1 1
(1 , x)n ln 1 , x = (Hn i , Hn ) n +i i xi ;
+
x = n xi ;
i   i  
+1

X n i
1 X1 i n!xi
=0 =0

xn = x; (ex , 1)n = i! ;
 n i1  i  i1 n
X i n!xi X i i
=0 =0

ln 1 ,1 x = (,4)(2Bi)!i x ;
2

= n i! ; x cot x 2

i i
X
1 X1
=0 =0
i,
= (,1)i, 2 (2 ,(21)i)!B i x ;
i i
= i1x ;
2 2 2 1

tan x 1 2
 (x)
i i
X1 (i) X1 (i)
=1 =1

1  ( x , 1)
 (x) =
i ix ;  (x) =
i ix ;
Y =1 =1

 (x) = 1 ,1p,x ; Stieltjes Integration

p
X 1 d(i) If G is continuous in the interval [a; b] and F is nondecreasing then
 (x) = where d ( n ) =
P 1 ;
Zb
j
2
i d n G(x) dF (x)
i x a
X
=1
1 P exists. If a  b  c then
 (x) (x , 1) = Sx(ii) where S (n) = djn d; Zc Zb Zc
i
n,
=1
G (x) dF (x) = G(x) dF (x) + G(x) dF (x):
= 2 (2njB n j  n ; n 2 N;
2 1 a a b
 (2n) )!
2 2
If the integrals involved exist
Z b,
dF (x) = Z b G(x) dF (x) + Z b H (x) dF (x);
x X 1 (4 i , 2)B i x i G ( x ) + H ( x)
= (,1)i,
2
1
; 2

sin x i (2i)! Zab ,
Zab Za b

 1 , p1 , 4x n X =0
1 n(2i + n , 1)! G(x) d F (x) + H (x) = G(x) dF (x) + G(x) dH (x);
= x i; a
2x i i!(n + i)! Z b Zb a,
Z ab
X c
G(x) dF (x) = G(x) d c
F (x) = c G(x) dF (x);
=0
1 2i= sin i
a a
ex sin x i; Z ba
2

= i ! x 4
Zb
s p i =1
G(x) dF (x) = G(b)F (b) , G(a)F (a) , F (x) dG(x):
1, 1,x X 1 (4 i )! i
a
F
a
F 0 at every
x = i p x; If the integrals involved exist, and possesses a derivative
i 16 2(2i)!(2i + 1)! point in [a; b] then
 arcsin x  2
X 4 i!
1
=0

i Zb Zb
i G(x) dF (x) = G(x)F 0 (x) dx:
2

x = (i + 1)(2i + 1)! x : 2

i =0
a a
Cramer's Rule Fibonacci Numbers
If we have equations:
00 47 18 76 29 93 85 34 61 52

a ; x + a ; x +


+ a ;n xn = b
1 1 1 1 2 2 1 1
86 11 57 28 70 39 94 45
1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; : : :
02 63

Denitions:
95 80 22 67 38 71 49 56 13 04

a ; x + a ; x +


+ a ;n xn = b
2 1 1 2 2 2 2 2 59 96 81 33 07 48 72 60 24 15

.. .. .. 73 69 90 82 44 17 58 01 Fi = Fi, +Fi, ; F = F = 1;
35 26 1 2 0 1

. . . F,i = (, 1)i, Fi;


1
68 74 09 91 83 55 27 12 46 30

an; x + an; x +


+ an;n xn = bn

1 1 2 2 37 08 75 19 92 84 66 23 50
Fi = p i , ^i ;
41
1

Let A = (ai;j ) and B be the column matrix (bi ). Then

14 25 36 40 51 62 03 77 88 99 5

there is a unique solution i det A 6= 0. Let Ai be A

21 32 43 54 65 06 10 89 Cassini's identity: for i > 0:
97 78

with column i replaced by B . Then

42 53 64 05 16 20 31 98 79
Fi Fi, , Fi = (,1)i :
87
+1 1
2

xi = det Ai : The Fibonacci number system: Additive rule:

det A Every integer n has a unique Fn k = Fk Fn + Fk, Fn ;
+ +1 1

representation F n = Fn Fn + Fn, Fn :
2 +1 1

Improvement makes strait roads, but the crooked n = Fk1 + Fk2 +


+ Fkm ; Calculation
roads without Improvement, are roads of Genius. where ki  ki + 2 for all i,  F F by matrices:  n
{ William Blake (The Marriage of Heaven and Hell)
+1 n, n, = 0 1 :
1  i < m and km  2.
2 1

Fn, Fn 1 1 1