Equation Cheatsheet

Theoretical Computer Science Cheat Sheet Definitions iff ∃ positive c, n0 such that 0 ≤ f (n) ≤ cg(n) ∀n ≥ n0 .

f (n) = O(g(n)) f (n) = Ω(g(n))

iff ∃ positive c, n0 such that f (n) ≥ cg(n) ≥ 0 ∀n ≥ n0 .

f (n) = Θ(g(n))

iff f (n) = O(g(n)) and f (n) = Ω(g(n)).

f (n) = o(g(n))

iff limn→∞ f (n)/g(n) = 0. iff ∀ > 0, ∃n0 such that |an − a| < , ∀n ≥ n0 .

lim an = a

n→∞

least b ∈ R such that b ≥ s, ∀s ∈ S.

sup S

greatest b ∈ R such that b ≤ s, ∀s ∈ S.

inf S

lim inf{ai | i ≥ n, i ∈ N}.

lim inf an

Series n X

i=

i=1

n(n + 1) , 2

n X

i2 =

i=1

n X

n(n + 1)(2n + 1) , 6

i3 =

i=1

n2 (n + 1)2 . 4

In general:   n n X X
1 im = (i + 1)m+1 − im+1 − (m + 1)im (n + 1)m+1 − 1 − m+1 i=1 i=1   n−1 m X 1 X m+1 im = Bk nm+1−k . m + 1 k i=1 k=0

Geometric series: n X cn+1 − 1 , ci = c−1 i=0 n X i=0

ici =

c 6= 1,

∞ X

ci =

i=0

ncn+2 − (n + 1)cn+1 + c , (c − 1)2

Harmonic series: n X 1 , Hn = i i=1

n X

1 , 1−c

c 6= 1,

∞ X

ci =

i=1 ∞ X

ici =

i=0

c , 1−c c , (1 − c)2

|c| < 1, |c| < 1.

n(n + 1) n(n − 1) Hn − . 2 4 lim sup an lim sup{ai | i ≥ n, i ∈ N}. i=1 n→∞ n→∞    n n   X X
n+1 i 1 n Combinations: Size k subHi = (n + 1)Hn − n, Hn+1 − . Hi = k m+1 m+1 m sets of a size n set. i=1 i=1 n       n   X Stirling numbers (1st kind): n n n n n! k n , 2. 1. = 3. = , =2 , Arrangements of an n elek k n−k (n − k)!k! k k=0           ment set into k cycles. n n−1 n−1 n n n−1 n , 5. = + , 4. = Stirling numbers (2nd kind): k k−1 k k k−1 k k          n  Partitions of an n element X r+k r+n+1 n m n n−k = , 6. = , 7. set into k non-empty sets. k n m k k m−k

n k=0      n   n   1st order Eulerian numbers: X X k k n+1 r s r+s = , 9. = , 8. Permutations π1 π2 . . . πn on m m+1 k n−k n k=0 k=0 {1, 2, . . . , n} with k ascents.         k−n−1 n n n

n  , 11. = = 1, 10. = (−1)k 2nd order Eulerian numbers. k k 1 n k         Cn Catalan Numbers: Binary n n−1 n−1 n n−1 − 1, 13. = k + , 12. = 2 trees with n + 1 vertices. k k k−1 2           n n n n n 14. = (n − 1)!, 15. = (n − 1)!Hn−1 , 16. = 1, 17. ≥ , 1 2 n k k               n   X 2n n 1 n n−1 n−1 n n n , = n!, 21. Cn = 18. = (n − 1) + , 19. = = , 20. n+1 n k k k k−1 n−1 n−1 2 k=0               n n n n n n−1 n−1 22. = = 1, 23. = , 24. = (k + 1) + (n − k) , 0 n−1 k n−1−k k k k−1       n   n n+1 0 n 1 if k = 0, 27. = 3n − (n + 1)2n + , 25. = 26. = 2n − n − 1, 2 2 k 1 0 otherwise   X    X   n   m  n   X n n x+k n n+1 n k 30. m! = , 29. = (m + 1 − k)n (−1)k , , 28. xn = m k n m k k n−m k=0 k=0 k=0        X n   n n n n−k n n−k−m k!, 32. = 1, 33. = 0 for n 6= 0, (−1) 31. = 0 n k m m k=0            n  X n n n−1 n−1 (2n)n , = 34. = (k + 1) + (2n − 1 − k) , 35. 2n k k k k−1 k=0      X    X    X n  n  n x+n−1−k n+1 n k k x , 37. = = (m + 1)n−k , 36. = k 2n k m m m+1 x−n n→∞

n→∞

k=0

iHi =

k

k=0

Theoretical Computer Science Cheat Sheet 

38. 40. 42. 44. 46. 48.



Identities Cont.   n X 1 k , nn−k = n! k! m m

X  n  k 



 n  X k



Trees

   n  X n x+k

Every tree with n vertices has n − 1 edges. Kraft inequality: If the depths of the leaves of a binary tree are d1 , . . . , dn : n X 2−di ≤ 1,

n+1 x = 39. = = , m+1 x−n k m k 2n k k=0 k=0 k=0   X      X   n n n+1 k+1 k n n−k , 41. = (−1) (−1)m−k , = m k m+1 k+1 m m k k     X     X m m n+k m+n+1 n+k m+n+1 k , 43. = k(n + k) , = k m k m k=0 k=0   X   X     n n n+1 n+1 k k = = (−1)m−k , 45. (n − m)! (−1)m−k , for n ≥ m, m m k+1 m k+1 m k   k X      X m − nm + n m + k  n m−n m+n m+k n = , 47. = , n−m m+k n+k k m+k n+k k n−m    k  X       k  X   k k n−k n n−k n n `+m n `+m , 49. = . = ` m k `+m ` m k ` `+m ` k

i=1

and equality holds only if every internal node has 2 sons.

k

Recurrences Master method: T (n) = aT (n/b) + f (n),

a ≥ 1, b > 1 logb a−

If ∃ > 0 such that f (n) = O(n then T (n) = Θ(nlogb a ).

)

If f (n) = Θ(nlogb a ) then T (n) = Θ(nlogb a log2 n). If ∃ > 0 such that f (n) = Ω(nlogb a+ ), and ∃c < 1 such that af (n/b) ≤ cf (n) for large n, then T (n) = Θ(f (n)). Substitution (example): Consider the following recurrence i Ti+1 = 22 · Ti2 , T1 = 2. Note that Ti is always a power of two. Let ti = log2 Ti . Then we have ti+1 = 2i + 2ti , t1 = 1. Let ui = ti /2i . Dividing both sides of the previous equation by 2i+1 we get 2i ti ti+1 = + i. i+1 i+1 2 2 2 Substituting we find u1 = 12 , ui+1 = 12 + ui , which is simply ui = i/2. So we find i−1 that Ti has the closed form Ti = 2i2 . Summing factors (example): Consider the following recurrence T (n) = 3T (n/2) + n, T (1) = 1. Rewrite so that all terms involving T are on the left side T (n) − 3T (n/2) = n. Now expand the recurrence, and choose a factor which makes the left side “telescope”


1 T (n) − 3T (n/2) = n


3 T (n/2) − 3T (n/4) = n/2 .. .. .. . . .
log2 n−1 3 T (2) − 3T (1) = 2 Let m = log2 n. Summing the left side we get T (n) − 3m T (1) = T (n) − 3m = T (n) − nk where k = log2 3 ≈ 1.58496. Summing the right side we get m−1 m−1 X n X
i i 3 3 = n . 2 i 2 i=0 i=0 Let c = 32 . Then we have  m  m−1 X c −1 i c =n n c−1 i=0

Multiply X X X and sum: gi+1 xi = 2gi xi + xi . i≥0

= 2n(clog2 n − 1) = 2n(c(k−1) logc n − 1) = 2nk − 2n, and so T (n) = 3n − 2n. Full history recurrences can often be changed to limited history ones (example): Consider i−1 X Ti = 1 + Tj , T0 = 1. j=0

Ti+1 = 1 +

i X

Tj .

j=0

Subtracting we find i i−1 X X Tj − 1 − Tj Ti+1 − Ti = 1 + j=0

= Ti . And so Ti+1 = 2Ti = 2i+1 .

i≥0

i≥0

P

We choose G(x) = i≥0 xi gi . Rewrite in terms of G(x): X G(x) − g0 = 2G(x) + xi . x i≥0

k

Note that

Generating functions: 1. Multiply both sides of the equation by xi . 2. Sum both sides over all i for which the equation is valid. 3. Choose a generatingPfunction ∞ G(x). Usually G(x) = i=0 xi gi . 3. Rewrite the equation in terms of the generating function G(x). 4. Solve for G(x). 5. The coefficient of xi in G(x) is gi . Example: gi+1 = 2gi + 1, g0 = 0.

j=0

Simplify: 1 G(x) = 2G(x) + . x 1−x Solve for G(x): x . G(x) = (1 − x)(1 − 2x) Expand this  using partial fractions:  1 2 − G(x) = x 1 − 2x 1 − x   X X 2i xi − xi  = x 2 =

X

i≥0 i+1

(2

i≥0

So gi = 2i − 1.

i≥0

− 1)x

i+1

.

Theoretical Computer Science Cheat Sheet π ≈ 3.14159,

e ≈ 2.71828,

γ ≈ 0.57721,

φ=

√ 1+ 5 2

i

2i

pi

General

1 2

2 4

2 3

Bernoulli Numbers (Bi = 0, odd i 6= 1):

3 4

8 16

5 7

5 6

32 64

11 13

7 8 9

128 256 512

17 19 23

10 11

1,024 2,048

29 31

12 13

4,096 8,192

37 41

14 15

16,384 32,768

43 47

16 17 18

65,536 131,072 262,144

53 59 61

19 20

524,288 1,048,576

67 71

21 22

2,097,152 4,194,304

73 79

23 24

8,388,608 16,777,216

83 89

25 26 27

33,554,432 67,108,864 134,217,728

97 101 103

28 29 30

268,435,456 536,870,912 1,073,741,824

107 109 113

31 32

2,147,483,648 4,294,967,296

127 131

Pascal’s Triangle 1 11 121 1331 14641 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1

− 21 ,

1 6,

1 − 30 ,

1 1 + 16 + 24 + 120 + ···   n x = ex . lim 1 + n→∞ n
n
n+1 . 1 + n1 < e < 1 + n1  
1 11e e n + −O 1 + n1 = e − . 2 2n 24n n3 Harmonic numbers: 25 137 49 363 761 7129 1, 32 , 11 6 , 12 , 60 , 20 , 140 , 280 , 2520 , . . .

1 2

ln n < Hn < ln n + 1,   1 Hn = ln n + γ + O . n Factorial, Stirling’s approximation: 1, 2, 6, 24, 120, 720, 5040, 40320, 362880,

...

 n    n 1 2πn . 1+Θ e n Ackermann’s  function and inverse: i=1  2j a(i, j) = a(i − 1, 2) j=1  a(i − 1, a(i, j − 1)) i, j ≥ 2 n! =

√ 1− 5 2

≈ −.61803

Probability

B2 = B4 = B0 = 1, B1 = 1 1 5 . B6 = 42 , B8 = − 30 , B10 = 66 Change of base, quadratic formula: √ −b ± b2 − 4ac loga x , . logb x = loga b 2a Euler’s number e: e=1+

φˆ =

≈ 1.61803,

√

α(i) = min{j | a(j, j) ≥ i}. Binomial distribution:   n k n−k , q = 1 − p, Pr[X = k] = p q k   n X n k n−k k p q = np. [X] = E k k=1

Poisson distribution: e−λ λk , E[X] = λ. Pr[X = k] = k! Normal (Gaussian) distribution: 2 2 1 e−(x−µ) /2σ , E[X] = µ. p(x) = √ 2πσ The “coupon collector”: We are given a random coupon each day, and there are n different types of coupons. The distribution of coupons is uniform. The expected number of days to pass before we to collect all n types is nHn .

Continuous distributions: If Z b p(x) dx, Pr[a < X < b] = a

then p is the probability density function of X. If Pr[X < a] = P (a), then P is the distribution function of X. If P and p both exist then Z a p(x) dx. P (a) = −∞

Expectation: If X is discrete X g(x) Pr[X = x]. E[g(X)] = x

If X continuous Z Z ∞ then g(x)p(x) dx = [g(X)] = E −∞

∞

g(x) dP (x).

−∞

Variance, standard deviation: VAR[X] = E[X 2 ] − E[X]2 , p σ = VAR[X]. For events A and B: Pr[A ∨ B] = Pr[A] + Pr[B] − Pr[A ∧ B] Pr[A ∧ B] = Pr[A] · Pr[B], iff A and B are independent. Pr[A ∧ B] Pr[A|B] = Pr[B] For random variables X and Y : E[X · Y ] = E[X] · E[Y ], if X and Y are independent. E[X + Y ] = E[X] + E[Y ], E[cX] = c E[X]. Bayes’ theorem: Pr[B|Ai ] Pr[Ai ] . Pr[Ai |B] = Pn j=1 Pr[Aj ] Pr[B|Aj ] Inclusion-exclusion: n n i X h_ Xi = Pr[Xi ] + Pr i=1

i=1 n X

X

(−1)k+1

k=2

ii <···
Pr

k h^

i Xij .

j=1

Moment inequalities:   1 Pr |X| ≥ λ E[X] ≤ , λ i h 1 Pr X − E[X] ≥ λ · σ ≤ 2 . λ Geometric distribution: q = 1 − p, Pr[X = k] = pq k−1 , ∞ X 1 kpq k−1 = . E[X] = p k=1

Theoretical Computer Science Cheat Sheet Trigonometry

Matrices

More Trig. C

Multiplication: (0,1)

b C

A

θ (-1,0)

C = A · B, (1,0)

c

a B Pythagorean theorem: C 2 = A2 + B 2 .

(0,-1)

cos a = B/C, sec a = C/B, cos a B cot a = = . sin a A circle: AB . A+B+C cos x =

1 + cot2 x = csc2 x,

cos x = − cos(π − x),

sin x = sin(π − x),
tan x = cot π2 − x ,

cot x = − cot(π − x),

csc x = cot x2 − cot x,

sin(x ± y) = sin x cos y ± cos x sin y, cos(x ± y) = cos x cos y ∓ sin x sin y,

cos 2x = cos2 x − sin2 x, cos 2x = 1 − 2 sin2 x,

n XY π i=1

Hyperbolic Functions Definitions: ex − e−x , sinh x = 2 x −x e −e tanh x = x , e + e−x 1 , sech x = cosh x

−x

x

e +e , 2 1 , csch x = sinh x 1 coth x = . tanh x cosh x =

Identities: cosh2 x − sinh2 x = 1,

tanh2 x + sech2 x = 1,

coth2 x − csch2 x = 1,

sinh(−x) = − sinh x, tanh(−x) = − tanh x,

cosh(x + y) = cosh x cosh y + sinh x sinh y,

2 tan x , 1 + tan2 x cos 2x = 2 cos2 x − 1, sin 2x =

cos 2x =

1 − tan2 x , 1 + tan2 x

cos(x + y) cos(x − y) = cos2 x − sin2 y. iπ

e

= −1.

c v2.02 1994 by Steve Seiden [email protected] http://www.csc.lsu.edu/~seiden

sinh 2x = 2 sinh x cosh x, cosh 2x = cosh2 x + sinh2 x, cosh x + sinh x = ex ,

cosh x − sinh x = e−x ,

(cosh x + sinh x)n = cosh nx + sinh nx, 2 sinh2 x2

= cosh x − 1,

θ

sin θ

0

0

π 6 π 4 π 3 π 2

1 2 √ 2 2 √ 3 2

1

cos θ 1

tan θ 0

√

√

0

1 √ 3 ∞

3 2 √ 2 2 1 2

3 3

2 cosh2 x2

a

A c Law of cosines:

B

c2 = a2 +b2 −2ab cos C. Area: A = 12 hc,

= 12 ab sin C,

c2 sin A sin B . 2 sin C Heron’s formula: =

sa = s − a, sb = s − b, sc = s − c.

ai,π(i) .

sinh(x + y) = sinh x cosh y + cosh x sinh y,

cot2 x − 1 2 tan x , cot 2x = tan 2x = 2 , 2 cot x 1 − tan x sin(x + y) sin(x − y) = sin2 x − sin2 y,

Euler’s equation: eix = cos x + i sin x,

Permanents:

h

√ A = s · sa · sb · sc , s = 12 (a + b + c),

aei + bf g + cdh − ceg − f ha − ibd.

=

cosh(−x) = cosh x,

tan x ± tan y , 1 ∓ tan x tan y cot x cot y ∓ 1 , cot(x ± y) = cot x ± cot y

tan(x ± y) =

sin 2x = 2 sin x cos x,

2 × 2 and 3 × 3 determinant: a b c d = ad − bc, a b c d e f = g b c − h a c + i a b e f d f d e g h i

1 , sec x

sin2 x + cos2 x = 1,

1 + tan2 x = sec2 x,
sin x = cos π2 − x ,

b

Determinants: det A 6= 0 iff A is non-singular. det A · B = det A · det B, n XY sign(π)ai,π(i) . det A =

perm A =

Identities: 1 , sin x = csc x 1 , tan x = cot x

ai,k bk,j .

k=1

π i=1

Definitions: sin a = A/C, csc a = C/A, A sin a = , tan a = cos a B Area, radius of inscribed 1 2 AB,

ci,j =

(cos θ, sin θ)

n X

n ∈ Z,

= cosh x + 1.

. . . in mathematics you don’t understand things, you just get used to them. – J. von Neumann

More identities: r 1 − cos x x , sin 2 = 2 r 1 + cos x , cos x2 = 2 r 1 − cos x , tan x2 = 1 + cos x 1 − cos x , = sin x sin x , = 1 + cos x r 1 + cos x , cot x2 = 1 − cos x 1 + cos x , = sin x sin x , = 1 − cos x eix − e−ix , sin x = 2i eix + e−ix , cos x = 2 eix − e−ix , tan x = −i ix e + e−ix e2ix − 1 , = −i 2ix e +1 sinh ix , sin x = i cos x = cosh ix, tanh ix . tan x = i

Theoretical Computer Science Cheat Sheet Number Theory The Chinese remainder theorem: There exists a number C such that: C ≡ r1 .. .. . .

mod m1 .. . C ≡ rn mod mn if mi and mj are relatively prime for i 6= j. Euler’s function: φ(x) is the number of positive integers Qnless than x relatively prime to x. If i=1 pei i is the prime factorization of x then n Y piei −1 (pi − 1). φ(x) = i=1

Euler’s theorem: If a and b are relatively prime then 1 ≡ aφ(b) mod b. Fermat’s theorem: 1 ≡ ap−1 mod p. The Euclidean algorithm: if a > b are integers then gcd(a, b) = gcd(a mod b, b). Qn If i=1 pei i is the prime factorization of x then n Y X piei +1 − 1 . d= S(x) = pi − 1 i=1 d|x

Perfect Numbers: x is an even perfect number iff x = 2n−1 (2n −1) and 2n −1 is prime. Wilson’s theorem: n is a prime iff (n − 1)! ≡ −1 mod n. M¨obius  inversion: 1 if i = 1.   0 if i is not square-free. µ(i) = r if i is the product of (−1)   r distinct primes. If G(a) =

X

F (d),

d|a

then F (a) =

X d|a

a . µ(d)G d

Prime numbers: ln ln n pn = n ln n + n ln ln n − n + n ln n   n , +O ln n n 2!n n + + π(n) = ln n (ln n)2 (ln n)3   n +O . (ln n)4

Graph Theory Definitions: Loop

An edge connecting a vertex to itself. Directed Each edge has a direction. Simple Graph with no loops or multi-edges. Walk A sequence v0 e1 v1 . . . e` v` . Trail A walk with distinct edges. Path A trail with distinct vertices. Connected A graph where there exists a path between any two vertices. Component A maximal connected subgraph. Tree A connected acyclic graph. Free tree A tree with no root. DAG Directed acyclic graph. Eulerian Graph with a trail visiting each edge exactly once. Hamiltonian Graph with a cycle visiting each vertex exactly once. Cut A set of edges whose removal increases the number of components. Cut-set A minimal cut. Cut edge A size 1 cut. k-Connected A graph connected with the removal of any k − 1 vertices. k-Tough ∀S ⊆ V, S 6= ∅ we have k · c(G − S) ≤ |S|. k-Regular A graph where all vertices have degree k. k-Factor A k-regular spanning subgraph. Matching A set of edges, no two of which are adjacent. Clique A set of vertices, all of which are adjacent. Ind. set A set of vertices, none of which are adjacent. Vertex cover A set of vertices which cover all edges. Planar graph A graph which can be embeded in the plane. Plane graph An embedding of a planar graph. X deg(v) = 2m. v∈V

If G is planar then n − m + f = 2, so f ≤ 2n − 4, m ≤ 3n − 6. Any planar graph has a vertex with degree ≤ 5.

Notation: E(G) Edge set V (G) Vertex set c(G) Number of components G[S] Induced subgraph deg(v) Degree of v ∆(G) Maximum degree δ(G) Minimum degree χ(G) Chromatic number χE (G) Edge chromatic number Complement graph Gc Complete graph Kn Kn1 ,n2 Complete bipartite graph r(k, `) Ramsey number Geometry Projective coordinates: triples (x, y, z), not all x, y and z zero. (x, y, z) = (cx, cy, cz) ∀c 6= 0. Cartesian Projective (x, y) (x, y, 1) y = mx + b (m, −1, b) x=c (1, 0, −c) Distance formula, Lp and L∞ metric: p (x1 − x0 )2 + (y1 − y0 )2 ,  1/p |x1 − x0 |p + |y1 − y0 |p ,   1/p . lim |x1 − x0 |p + |y1 − y0 |p p→∞

Area of triangle (x0 , y0 ), (x1 , y1 ) and (x2 , y2 ): x1 − x0 y1 − y0 1 . 2 abs x − x 2 0 y2 − y0 Angle formed by three points: (x2 , y2 ) `2 θ (x1 , y1 ) `1 (0, 0) (x1 , y1 ) · (x2 , y2 ) cos θ = . `1 `2 Line through two points (x0 , y0 ) and (x1 , y1 ): x y 1 x0 y0 1 = 0. x1 y1 1 Area of circle, volume of sphere: A = πr2 ,

V = 43 πr3 .

If I have seen farther than others, it is because I have stood on the shoulders of giants. – Issac Newton

Theoretical Computer Science Cheat Sheet π

Calculus

Wallis’ identity: 2 · 2 · 4 · 4 · 6 · 6··· π =2· 1 · 3 · 3 · 5 · 5 · 7··· Brouncker’s continued fraction expansion: 12 π 4 =1+ 32 2+ 52 2+

Gregrory’s series: π 1 4 =1− 3 +

1 5

−

1 7

2+

72 2+···

+

1 9

− ···

Derivatives: 1.

du d(cu) =c , dx dx

4.

du d(un ) = nun−1 , dx dx

7.

du d(cu ) = (ln c)cu , dx dx

9.

du d(sin u) = cos u , dx dx

Newton’s series: 1 1 1·3 π 6 = 2 + 2 · 3 · 23 + 2 · 4 · 5 · 25 + · · · Sharp’s series: π 6

 1 1 1 1  + 2 − 3 +··· = √ 1− 1 3 ·3 3 ·5 3 ·7 3

Euler’s series: π2 6 π2 8 π2 12

= = =

1 12 1 12 1 12

+ + −

1 22 1 32 1 22

+ + +

1 32 1 52 1 32

1 42 1 72 1 42

+ + −

+ + +

1 52 1 92 1 52

+ ··· + ··· − ···

Partial Fractions Let N (x) and D(x) be polynomial functions of x. We can break down N (x)/D(x) using partial fraction expansion. First, if the degree of N is greater than or equal to the degree of D, divide N by D, obtaining N 0 (x) N (x) = Q(x) + , D(x) D(x) where the degree of N 0 is less than that of D. Second, factor D(x). Use the following rules: For a non-repeated factor: A N 0 (x) N (x) = + , (x − a)D(x) x−a D(x) where



N (x) A= D(x)

   1 dk N (x) . Ak = k! dxk D(x) x=a

The reasonable man adapts himself to the world; the unreasonable persists in trying to adapt the world to himself. Therefore all progress depends on the unreasonable. – George Bernard Shaw

14.

1 du d(arcsec u) = √ , 2 dx u 1 − u dx du d(sinh u) = cosh u , 21. dx dx 23.

du d(tanh u) = sech2 u , dx dx

25.

du d(sech u) = − sech u tanh u , dx dx

20.

26.

1 du d(arcsinh u) =√ , 2 dx 1 + u dx 1 du d(arctanh u) = , 29. dx 1 − u2 dx

32.

Z n 6= −1,

4.

sin x dx = − cos x,

d(arccsc u) −1 du = √ , 2 dx u 1 − u dx d(cosh u) du 22. = sinh u , dx dx d(coth u) du = − csch2 u , dx dx

d(csch u) du = − csch u coth u , dx dx

d(arccsch u) −1 du √ = . dx |u| 1 + u2 dx Z (u + v) dx =

v dx,

Z tan x dx = − ln | cos x|,

11.

Z

cot x dx = ln | cos x|,

Z sec x dx = ln | sec x + tan x|,

Z 14.

Z u dx +

Z 1 dx = ln x, 5. ex dx = ex , x Z Z du dv 7. u dx = uv − v dx, dx dx Z 9. cos x dx = sin x,

Z

12.

d(cot u) du = csc2 u , dx dx

Z 2.

dx = arctan x, 1 + x2

10.

d(cos u) du = − sin u , dx dx

d(arccosh u) 1 du =√ , 2 dx u − 1 dx d(arccoth u) 1 du 30. = 2 , dx u − 1 dx

−1 du d(arcsech u) = √ , dx u 1 − u2 dx Integrals: Z Z 1. cu dx = c u dx,

Z

d(ln u) 1 du = , dx u dx

28.

31.

8.

du d(ecu ) = cecu , dx dx

d(csc u) du = − cot u csc u , dx dx

24.

27.

6.

6.

,

16.

19.

Z

d(uv) dv du =u +v , dx dx dx

d(arccos u) −1 du =√ , dx 1 − u2 dx d(arccot u) −1 du 18. = , dx 1 + u2 dx

1 du d(arcsin u) =√ , 2 dx 1 − u dx 1 du d(arctan u) = , 17. dx 1 + u2 dx

3.




12.

15.

x=a

k=0

where

du d(sec u) = tan u sec u , dx dx

1 xn+1 , x dx = n+1

dv dx

10.

13.

n

3.

8.

du d(tan u) = sec2 u , dx dx

Z

For a repeated factor: m−1 X Ak N 0 (x) N (x) = , + m m−k (x − a) D(x) (x − a) D(x)

d(u + v) du dv = + , dx dx dx
v du d(u/v) dx − u 5. = dx v2

11.

 .

2.

arcsin xa dx = arcsin xa +

p a2 − x2 ,

13. a > 0,

csc x dx = ln | csc x + cot x|,

Theoretical Computer Science Cheat Sheet Z 15.

arccos Z

17. Z 19. Z

x a dx

= arccos

sin2 (ax)dx =

1 2a

x a

−

p

Calculus Cont. a2

−

x2 ,

Z

16.

a > 0,

arctan xa dx = x arctan xa − Z


ax − sin(ax) cos(ax) ,

18.

cos2 (ax)dx =

1 2a

a 2

a > 0,


ax + sin(ax) cos(ax) , Z

sec2 x dx = tan x,

ln(a2 + x2 ),

20.

csc2 x dx = − cot x,

Z Z Z sinn−1 x cos x n − 1 cosn−1 x sin x n − 1 + sinn−2 x dx, + cosn−2 x dx, 22. cosn x dx = n n n n Z Z Z tann−1 x cotn−1 x n n−2 n − tan − cotn−2 x dx, n 6= 1, x dx, n 6= 1, 24. cot x dx = − tan x dx = n−1 n−1 Z tan x secn−1 x n − 2 + secn−2 x dx, n 6= 1, secn x dx = n−1 n−1 Z Z Z cot x cscn−1 x n − 2 + cscn−2 x dx, n 6= 1, 27. sinh x dx = cosh x, 28. cosh x dx = sinh x, cscn x dx = − n−1 n−1 Z Z Z tanh x dx = ln | cosh x|, 30. coth x dx = ln | sinh x|, 31. sech x dx = arctan sinh x, 32. csch x dx = ln tanh x2 , sinn x dx = −

21. Z 23. Z 25. Z 26. Z 29. Z 33.

2

sinh x dx =

1 4

sinh(2x) −

Z 36.

arcsinh

x a dx

= x arcsinh

x a

Z

1 2 x,

−

34.

2

cosh x dx =

1 4

sinh(2x) +

1 2 x,

Z 35.

sech2 x dx = tanh x,

Z

p

x2

+

a2 ,

a > 0,

37.

arctanh xa dx = x arctanh xa +

a 2

ln |a2 − x2 |,

 x p  x arccosh − x2 + a2 , if arccosh xa > 0 and a > 0, a 38. arccosh xa dx = p  x arccosh x + x2 + a2 , if arccosh x < 0 and a > 0, a a Z   p dx √ = ln x + a2 + x2 , a > 0, 39. a2 + x2 Z p Z p 2 dx 1 x = arctan , a > 0, 41. a2 − x2 dx = x2 a2 − x2 + a2 arcsin xa , a > 0, 40. a a 2 2 a +x Z p 4 42. (a2 − x2 )3/2 dx = x8 (5a2 − 2x2 ) a2 − x2 + 3a8 arcsin xa , a > 0, Z Z Z a + x 1 x dx dx dx x , √ ln = arcsin a , a > 0, 44. = = √ , 43. 45. 2 2 2 2 3/2 2 2 2 a −x 2a a−x (a − x ) a −x a a2 − x2 Z Z p p p p 2 dx √ 47. a2 ± x2 dx = x2 a2 ± x2 ± a2 ln x + a2 ± x2 , = ln x + x2 − a2 , a > 0, 46. x2 − a2 Z Z √ 1 x 2(3bx − 2a)(a + bx)3/2 dx , 49. x a + bx dx = = ln , 48. 2 ax + bx a a + bx 15b2 √ √ Z Z Z √ √ a + bx − a x 1 a + bx 1 √ √ dx = 2 a + bx + a dx, 51. dx = √ ln √ 50. √ , a > 0, x x a + bx a + bx a + bx + a 2 Z p Z √ 2 a + √a2 − x2 p a − x2 2 2 53. x a2 − x2 dx = − 13 (a2 − x2 )3/2 , 52. dx = a − x − a ln , x x Z Z a + √a2 − x2 p p 4 dx √ 55. = − a1 ln 54. x2 a2 − x2 dx = x8 (2x2 − a2 ) a2 − x2 + a8 arcsin xa , a > 0, , 2 2 x a −x Z Z 2 p p 2 x dx x dx x √ √ 56. = − a2 − x2 , 57. = − x2 a2 − x2 + a2 arcsin a, a > 0, 2 2 2 2 a −x a − x √ √ √ Z Z a + a2 + x2 p p a2 + x2 x2 − a2 a 59. dx = a2 + x2 − a ln dx = x2 − a2 − a arccos |x| , a > 0, 58. , x x x Z Z p dx x , √ √ 61. = a1 ln 60. x x2 ± a2 dx = 13 (x2 ± a2 )3/2 , x x2 + a2 a + a2 + x2 Z

Theoretical Computer Science Cheat Sheet Z 62. Z 64. Z 66.

Z 67. Z 68.

Calculus Cont.

√ x2 ± a2 dx dx 1 a √ √ , = a arccos |x| , a > 0, 63. =∓ a2 x x x2 − a2 x2 x2 ± a2 √ Z p x2 ± a2 (x2 + a2 )3/2 x dx √ = x2 ± a2 , 65. dx = ∓ , x4 3a2 x3 x2 ± a2  √ 2ax + b − b2 − 4ac  1   √ √ ln , if b2 > 4ac,  2 2 dx b − 4ac 2ax + b + b − 4ac = ax2 + bx + c   2ax + b 2  √ arctan √ , if b2 < 4ac, 4ac − b2 4ac − b2  √ p 1   √ ln 2ax + b + 2 a ax2 + bx + c , if a > 0,  a dx √ = −2ax − b 1 ax2 + bx + c   √ , if a < 0, arcsin √ −a b2 − 4ac Z p dx 2ax + b p 2 4ax − b2 √ , ax2 + bx + c dx = ax + bx + c + 2 4a 8a ax + bx + c Z

√

Z b ax2 + bx + c dx √ − , 69. 2 a 2a ax + bx + c √ √  −1 2 c ax2 + bx + c + bx + 2c    , Z  √c ln x dx √ = 70. 2  x ax + bx + c  1 bx + 2c   √ arcsin √ , −c |x| b2 − 4ac Z p 2 2 a )(x2 + a2 )3/2 , 71. x3 x2 + a2 dx = ( 13 x2 − 15 Z

Z 72. Z 73.

x dx √ = 2 ax + bx + c

xn sin(ax) dx = − a1 xn cos(ax) + n

x cos(ax) dx = Z

74.

xn eax dx = Z

75.

xn eax − a

sin(ax) − Z n a



xn ln(ax) dx = xn+1 Z

76.

1 n ax

xn (ln ax)m dx =

n a

if c > 0, if c < 0,

Z

E f (x) = f (x + 1). Fundamental Theorem: X f (x) = ∆F (x) ⇔ f (x)δx = F (x) + C. b X

n−1

x

1 ln(ax) − n+1 (n + 1)2

n+1

x m (ln ax)m − n+1 n+1

f (x)δx =

b−1 X

a

Differences: ∆(cu) = c∆u,

f (i).

i=a

∆(u + v) = ∆u + ∆v,

∆(uv) = u∆v + E v∆u, ∆(xn ) = nxn−1 , ∆(Hx ) = x−1 ,

∆(2x ) = 2x ,

x x ∆ m = m−1 .

∆(cx ) = (c − 1)cx , Sums: P P cu δx = c u δx, P P P (u + v) δx = u δx + v δx, P P u∆v δx = uv − E v∆u δx, n+1 P −1 P n x δx = Hx , x δx = xm+1 ,

P P x x x x c , c δx = c−1 m δx = m+1 . Falling Factorial Powers: xn = x(x − 1) · · · (x − n + 1), n > 0, xn =

Z sin(ax) dx,

1 , (x + 1) · · · (x + |n|)

n < 0,

xn+m = xm (x − m)n . Rising Factorial Powers:

xn−1 eax dx,

xn = x(x + 1) · · · (x + n − 1),



n > 0,

x0 = 1,

, Z

xn = xn (ln ax)m−1 dx.

x1 = x2 =

x1 x2 + x1

= =

x1 x2 − x1

x3 = x4 =

x3 + 3x2 + x1 4 x + 6x3 + 7x2 + x1

= =

x3 − 3x2 + x1 4 x − 6x3 + 7x2 − x1

x5 =

x5 + 15x4 + 25x3 + 10x2 + x1

=

x5 − 15x4 + 25x3 − 10x2 + x1

x1 = x2 =

x1 x + x1

x1 = x2 =

x1 x − x1

x3 = x4 =

x3 + 3x2 + 2x1 x4 + 6x3 + 11x2 + 6x1

x3 = x4 =

x3 − 3x2 + 2x1 x4 − 6x3 + 11x2 − 6x1

x5 =

x5 + 10x4 + 35x3 + 50x2 + 24x1

x5 =

x5 − 10x4 + 35x3 − 50x2 + 24x1

2

Difference, shift operators: ∆f (x) = f (x + 1) − f (x),

x0 = 1,

xn−1 cos(ax) dx,

n a

Finite Calculus

2

1 , (x − 1) · · · (x − |n|)

n < 0,

xn+m = xm (x + m)n . Conversion: xn = (−1)n (−x)n = (x − n + 1)n = 1/(x + 1)−n , xn = (−1)n (−x)n = (x + n − 1)n = 1/(x − 1)−n , n   n   X n k X n x = (−1)n−k xk , xn = k k k=1 k=1 n   X n (−1)n−k xk , xn = k k=1 n   X n k n x . x = k k=1

Theoretical Computer Science Cheat Sheet Series Taylor’s series:

∞

X (x − a)i (x − a)2 00 f (a) + · · · = f (i) (a). f (x) = f (a) + (x − a)f (a) + 2 i! i=0 Expansions: ∞ X 1 = 1 + x + x2 + x3 + x4 + · · · = xi , 1−x i=0 ∞ X 1 = 1 + cx + c2 x2 + c3 x3 + · · · = ci xi , 1 − cx i=0 ∞ X 1 n 2n 3n = 1 + x + x + x + · · · = xni , 1 − xn i=0 ∞ X x 2 3 4 = x + 2x + 3x + 4x + · · · = ixi , (1 − x)2 i=0   ∞ X 1 dn in xi , = x + 2n x2 + 3n x3 + 4n x4 + · · · = xk n dx 1−x i=0 ∞ X xi , = 1 + x + 12 x2 + 16 x3 + · · · = ex i! i=0 ∞ X xi = (−1)i+1 , ln(1 + x) = x − 12 x2 + 13 x3 − 14 x4 − · · · i i=1 ∞ i Xx 1 = x + 12 x2 + 13 x3 + 14 x4 + · · · , = ln 1−x i i=1 ∞ X x2i+1 1 3 1 5 1 7 , (−1)i sin x = x − 3! x + 5! x − 7! x + · · · = (2i + 1)! i=0 ∞ X x2i 1 2 1 4 1 6 , x + 4! x − 6! x + ··· = (−1)i cos x = 1 − 2! (2i)! i=0 ∞ X x2i+1 , = x − 13 x3 + 15 x5 − 17 x7 + · · · = (−1)i tan−1 x (2i + 1) i=0 ∞   X n i 2 = 1 + nx + n(n−1) x + · · · = (1 + x)n x, 2 i i=0  ∞  X
i+n i 1 n+2 2 = 1 + (n + 1)x + 2 x + · · · = x, (1 − x)n+1 i i=0 ∞ X Bi xi x 1 1 2 1 4 = 1 − , x + x − x + · · · = 2 12 720 x e −1 i! i=0   ∞ X √ 2i i 1 1 2 3 (1 − 1 − 4x) = 1 + x + 2x + 5x + · · · = x, 2x i+1 i i=0 ∞   X 2i i 1 √ = 1 + x + 2x2 + 6x3 + · · · = x, i 1 − 4x i=0 √  n  ∞  X
1 − 1 − 4x 2i + n i 1 4+n 2 √ = 1 + (2 + n)x + 2 x + · · · = x, 2x i 1 − 4x i=0 ∞ X 1 1 25 4 3 ln = x + 32 x2 + 11 x + x + · · · = Hi xi , 6 12 1−x 1−x i=1  2 ∞ X Hi−1 xi 1 1 4 , = 12 x2 + 34 x3 + 11 x + · · · = ln 24 2 1−x i i=2 ∞ X x 2 3 4 = x + x + 2x + 3x + · · · = Fi xi , 1 − x − x2 i=0 ∞ X Fn x 2 3 = F x + F x + F x + · · · = Fni xi . n 2n 3n 1 − (Fn−1 + Fn+1 )x − (−1)n x2 i=0 0

Ordinary power series: ∞ X ai xi . A(x) = i=0

Exponential power series: ∞ X xi ai . A(x) = i! i=0 Dirichlet power series: ∞ X ai . A(x) = ix i=1 Binomial theorem: n   X n n−k k y . x (x + y)n = k k=0

Difference of like powers: n−1 X xn−1−k y k . xn − y n = (x − y) k=0

For ordinary power series: ∞ X (αai + βbi )xi , αA(x) + βB(x) = i=0

xk A(x) = A(x) −

Pk−1 i=0 xk

∞ X

ai−k xi ,

i=k i

ai x

A(cx) =

=

∞ X

∞ X

ai+k xi ,

i=0

ci ai xi ,

i=0

∞ X (i + 1)ai+1 xi , A0 (x) = i=0

xA0 (x) =

∞ X

iai xi ,

i=1

Z A(x) dx =

∞ X ai−1 i=1

A(x) + A(−x) = 2 A(x) − A(−x) = 2

∞ X

i

xi ,

a2i x2i ,

i=0

∞ X

a2i+1 x2i+1 .

i=0

Pi Summation: If bi = j=0 ai then 1 A(x). B(x) = 1−x Convolution:   ∞ i X X  aj bi−j  xi . A(x)B(x) = i=0

j=0

God made the natural numbers; all the rest is the work of man. – Leopold Kronecker

Theoretical Computer Science Cheat Sheet Series Expansions: 1 1 ln n+1 (1 − x) 1−x xn 

1 ln 1−x

n

tan x 1 ζ(x) ζ(x) ζ 2 (x)

Escher’s Knot

   −n ∞   X n+i i 1 i = (Hn+i − Hn ) x, = xi , i x n i=0 i=0 ∞   ∞   X X n i i n!xi x n , = (e − 1) = x, i! i n i=0 i=0 ∞   ∞ X X i n!xi (−4)i B2i x2i , x cot x = , = (2i)! n i! i=0 i=0 ∞ ∞ 2i 2i 2i−1 X X 1 i−1 2 (2 − 1)B2i x , ζ(x) = (−1) , = x (2i)! i i=1 i=1 ∞ ∞ X X µ(i) φ(i) ζ(x − 1) = = , , x i ζ(x) ix i=1 i=1 Y 1 = , Stieltjes Integration 1 − p−x p If G is continuous in the interval [a, b] and F is nondecreasing then ∞ X Z b P d(i) = where d(n) = d|n 1, G(x) dF (x) xi ∞ X

i=1

ζ(x)ζ(x − 1)

=

∞ X S(i)

xi

where S(n) =

P d|n

d,

i=1 2n−1

ζ(2n) x sin x √ n  1 − 1 − 4x 2x x

e sin x

|B2n | 2n π , n ∈ N, = (2n)! ∞ X (4i − 2)B2i x2i = , (−1)i−1 (2i)! i=0 2

= =

√ 1−x x 2  arcsin x x

∞ X n(2i + n − 1)! i=0 ∞ X i=1

s

1−

exists. If a ≤ b ≤ c then Z Z c G(x) dF (x) =

=

∞ X i=0

=

∞ X i=0

i!(n + i)! i/2

2

sin i!

iπ 4

xi ,

i

x,

(4i)! √ xi , i 16 2(2i)!(2i + 1)! 4i i!2 x2i . (i + 1)(2i + 1)!

Cramer’s Rule If we have equations: a1,1 x1 + a1,2 x2 + · · · + a1,n xn = b1 a2,1 x1 + a2,2 x2 + · · · + a2,n xn = b2 .. .. .. . . . an,1 x1 + an,2 x2 + · · · + an,n xn = bn Let A = (ai,j ) and B be the column matrix (bi ). Then there is a unique solution iff det A 6= 0. Let Ai be A with column i replaced by B. Then det Ai . xi = det A Improvement makes strait roads, but the crooked roads without Improvement, are roads of Genius. – William Blake (The Marriage of Heaven and Hell)

a

a

Z

b

a

Z

b


G(x) d F (x) + H(x) =

a

Z

b

Z c · G(x) dF (x) =

a

G(x) dF (x). b

If the integrals involved exist Z Z b
G(x) + H(x) dF (x) = a

c

G(x) dF (x) +

Z

b

a

Z

b


G(x) d c · F (x) = c

a

Z

b

b

G(x) dF (x) + a

b

H(x) dF (x),

a

Z

b

G(x) dF (x) +

G(x) dH(x), a Z b

G(x) dF (x),

Z

G(x) dF (x) = G(b)F (b) − G(a)F (a) −

a

a b

F (x) dG(x). a

If the integrals involved exist, and F possesses a derivative F 0 at every point in [a, b] then Z b Z b G(x) dF (x) = G(x)F 0 (x) dx. a 00 47 18 76 29 93 85 34 61 52 86 11 57 28 70 39 94 45 02 63 95 80 22 67 38 71 49 56 13 04 59 96 81 33 07 48 72 60 24 15 73 69 90 82 44 17 58 01 35 26 68 74 09 91 83 55 27 12 46 30 37 08 75 19 92 84 66 23 50 41 14 25 36 40 51 62 03 77 88 99

a

Fibonacci Numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . . Definitions: Fi = Fi−1 +Fi−2 , F0 = F1 = 1, F−i = (−1)i−1 Fi ,   Fi = √1 φi − φˆi , 5

21 32 43 54 65 06 10 89 97 78

Cassini’s identity: for i > 0:

42 53 64 05 16 20 31 98 79 87

Fi+1 Fi−1 − Fi2 = (−1)i . Additive rule:

The Fibonacci number system: Every integer n has a unique representation n = Fk1 + Fk2 + · · · + Fkm , where ki ≥ ki+1 + 2 for all i, 1 ≤ i < m and km ≥ 2.

Fn+k = Fk Fn+1 + Fk−1 Fn , F2n = Fn Fn+1 + Fn−1 Fn . Calculation by matrices:   n  0 1 Fn−2 Fn−1 . = Fn−1 Fn 1 1