Theoretical Computer Science Cheat Sheet Definitions Series f(n) = O ... [PDF]

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 (i + 1)m+1 − im+1 − (m + 1)im (n + 1)m+1 − 1 − im = 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
1 i n+1 n Combinations: Size k subHi = Hn+1 − Hi = (n + 1)Hn − n, . k m m+1 m+1 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. =2 , 3. = , 1. = Arrangements of an n ele(n − k)!k! k k n−k k k=0           ment set into k cycles. n n n−1 n−1 n n−1 n , 5. 4. = = + , Stirling numbers (2nd kind): k k−1 k k k k−1 k          n  Partitions of an n element X n m n n−k r+k r+n+1 6. = , 7. = , set into k non-empty sets. m k k m−k k n

n k=0      n   n   1st order Eulerian numbers: X X k k n+1 r s r+s 8. = , 9. = , 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 n−1 n−1 n−1 12. = 2 − 1, 13. = k + , trees with n + 1 vertices. 2 k k k−1           n n n n n 14. = (n − 1)!, 15. = (n − 1)!Hn−1 , 16. = 1, 17. ≥ , 1 2 n k k               n   X 2n 1 n n−1 n−1 n n n n , 18. = (n − 1) + , 19. = = , 20. = n!, 21. Cn = n+1 n k k k−1 n−1 n−1 2 k 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 0 n+1 1 if k = 0, 26. = 2n − n − 1, 27. 25. = 3n − (n + 1)2n + = , 1 2 k 2 0 otherwise    X    X  n   m  n   X n x+k n n+1 n n k 28. xn = , 29. = (m + 1 − k)n (−1)k , 30. m! = , k n m k m k n−m k=0 k=0 k=0   X      n   n n n−k n n n−k−m 31. = (−1) k!, 32. = 1, 33. = 0 for n 6= 0, m k m 0 n k=0          n  X n n−1 (2n)n n−1 n , 34. = (k + 1) + (2n − 1 − k) , 35. = 2n k k k−1 k k=0   X      X    X  n  n  x n x+n−1−k n+1 n k k 36. = , 37. = = (m + 1)n−k , x−n k 2n m+1 k m m 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

Trees

   n  X x n x+k n+1 39. = , = = x−n k 2n m+1 k m k=0 k=0 k k=0   X      X   n n k+1 n n+1 k n−k = (−1) , 41. = (−1)m−k , m k m+1 m k+1 m k k       X   X m m n+k n+k m+n+1 m+n+1 k(n + k) , k , 43. = = k k m m k=0 k=0   X     X   n n+1 k n n+1 k = (−1)m−k , 45. (n − m)! = (−1)m−k , for n ≥ m, m k+1 m 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 n−m m+k n+k k   k  X      k  X     n ℓ+m k n−k n n ℓ+m k n−k n = , 49. = . ℓ+m ℓ ℓ m k ℓ+m ℓ ℓ m k 



X  n  k 

 n  X k



Every tree with n vertices has n − 1 edges.



k

Kraft inequality: If the depths of the leaves of a binary tree are d1 , . . . , dn : n X 2−di ≤ 1, 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

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

log b 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 ti+1 2i ti = + i. i+1 i+1 2 2 2 Substituting we find ui+1 = 21 + ui , u1 = 12 , 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
i X n i 3 3 = n . 2 i 2 i=0 i=0 Let c = 23 . Then we have  m  m−1 X c −1 i c =n n c−1 i=0

= 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 Tj , T0 = 1. Ti = 1 + j=0

Ti+1 = 1 +

Tj .

j=0

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

= Ti .

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

i≥0

i≥0

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

i≥0

k

i X

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

= 2n(clog2 n − 1)

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 i G(x). Usually G(x) = ∞ i=0 x 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: G(x) 1 = 2G(x) + . x 1−x

Solve for G(x): G(x) =

x . (1 − x)(1 − 2x)

Expand this  using partial fractions:  1 2 − G(x) = x 1 − 2x 1 − x   X X = x 2 2i xi − xi  i≥0

=

X

(2

i≥0

So gi = 2i − 1.

i+1

i≥0

i+1

− 1)x

.

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

3 4

8 16

5 7

Bernoulli Numbers (Bi = 0, odd i 6= 1): 1 , B0 = 1, B1 = − 21 , B2 = 61 , B4 = − 30 1 1 5 B6 = 42 , B8 = − 30 , B10 = 66 .

5 6

32 64

11 13

7 8

128 256

17 19

9 10

512 1,024

23 29

11 12

2,048 4,096

31 37

13 14

8,192 16,384

41 43

15

32,768

47

16 17

65,536 131,072

53 59

18 19

262,144 524,288

61 67

20 21

1,048,576 2,097,152

71 73

22 23

4,194,304 8,388,608

79 83

24 25

16,777,216 33,554,432

89 97

26 27

67,108,864 134,217,728

101 103

28

268,435,456

107

29 30

536,870,912 1,073,741,824

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

1 1 + 61 + 24 + 120 + ···   n x lim 1 + = ex . n→∞ n
n
n+1 1 + n1 < e < 1 + n1 .  
11e 1 e n 1 + n1 = e − . −O + 2 2n 24n n3 Harmonic numbers:

1, 23 ,

1 2

11 25 137 49 363 761 7129 6 , 12 , 60 , 20 , 140 , 280 , 2520 , . . .

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,

√ 1− 5 2

≈ −.61803

Probability

Change of base, quadratic formula: √ −b ± b2 − 4ac loga x , . logb x = loga b 2a Euler’s number e: e=1+

φˆ =

≈ 1.61803,

...

   n  √ 1 n 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! =

α(i) = min{j | a(j, j) ≥ i}.

Binomial distribution:   n k n−k Pr[X = k] = p q , q = 1 − p, k   n X n k n−k [X] = k p q = np. E k k=1

Poisson distribution: e−λ λk , E[X] = λ. Pr[X = k] = k! Normal (Gaussian) distribution: 2 2 1 p(x) = √ e−(x−µ) /2σ , E[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 Pr[a < X < b] = p(x) dx, 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 ∞ then Z [g(X)] = g(x)p(x) dx = 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[B] For random variables X and Y : E[X · Y ] = E[X] · E[Y ], if X and Y are independent. Pr[A|B] =

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_ Pr[Xi ] + Xi = Pr i=1

i=1

n X

k=2

(−1)k+1

X

ii 0,

Z

Z

cot x dx = ln | cos x|,

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

Theoretical Computer Science Cheat Sheet Calculus Cont. 15. 17. 19. 21. 23. 25. 26. 29. 33. 36.

Z

Z

Z

Z

Z

Z

Z

Z

Z

Z

arccos

x a dx

= arccos

sin2 (ax)dx =

1 2a

x a

p − a2 − x2 ,

a > 0,

16.

Z

arctan xa dx = x arctan xa −


ax − sin(ax) cos(ax) ,

18.

Z

sec2 x dx = tan x,

cos2 (ax)dx =

1 2a

20.

a 2

ln(a2 + x2 ),

a > 0,


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

csc2 x dx = − cot x,

Z

sech2 x dx = tanh x,

Z Z Z sinn−1 x cos x n − 1 cosn−1 x sin x n − 1 + + sinn−2 x dx, 22. cosn x dx = cosn−2 x dx, n n n n Z Z Z tann−1 x cotn−1 x n n−2 n tan x dx = − tan x dx, n 6= 1, 24. cot x dx = − − cotn−2 x dx, n 6= 1, n−1 n−1 Z tan x secn−1 x n − 2 + secn x dx = secn−2 x dx, n 6= 1, n−1 n−1 Z Z Z cot x cscn−1 x n − 2 cscn x dx = − + cscn−2 x dx, n 6= 1, 27. sinh x dx = cosh x, 28. cosh x dx = sinh x, 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 = −

2

sinh x dx = arcsinh

x a dx

1 4

sinh(2x) −

= x arcsinh

x a

1 2 x,

p − x2 + a2 ,

34.

Z

a > 0,

2

cosh x dx =

1 4

sinh(2x) + 37.

Z

1 2 x,

35.

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 Z p p 2 dx 1 x = a arctan a , a > 0, 40. 41. a2 − x2 dx = x2 a2 − x2 + a2 arcsin xa , a > 0, 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 dx dx 1 dx x x , √ = arcsin a , a > 0, , 45. 43. = ln 44. = √ 2 2 2 2 3/2 2 2 2 a −x 2a a−x (a − x ) a −x a a2 − x2 Z p Z p p p 2 dx √ a2 ± x2 dx = x2 a2 ± x2 ± a2 ln x + a2 ± x2 , 46. = ln x + x2 − a2 , a > 0, 47. x2 − a2 Z Z √ 2(3bx − 2a)(a + bx)3/2 1 x dx , = ln , 49. x a + bx dx = 48. 2 ax + bx a a + bx 15b2 √ √ Z Z Z √ √ a + bx − a a + bx 1 x 1 √ √ dx, 51. dx = √ ln √ 50. dx = 2 a + bx + a √ , 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 , dx = a − x − a ln 52. , x x Z Z a + √a2 − x2 p p 4 dx √ 54. x2 a2 − x2 dx = x8 (2x2 − a2 ) a2 − x2 + a8 arcsin xa , a > 0, = − a1 ln 55. , 2 2 x a −x Z Z 2 p p 2 x dx x dx x √ √ = − a2 − x2 , = − x2 a2 − x2 + a2 arcsin a, 57. a > 0, 56. 2 2 2 2 a −x a − x √ √ √ Z Z a + a2 + x2 p p a2 + x2 x2 − a2 a dx = a2 + x2 − a ln dx = x2 − a2 − a arccos |x| 59. 58. , a > 0, , x x x Z Z p dx x , √ √ 61. 60. x x2 ± a2 dx = 31 (x2 ± a2 )3/2 , = a1 ln x x2 + a2 a + a2 + x2 Z

Theoretical Computer Science Cheat Sheet Calculus Cont.

62.

Z

64.

Z

66.

Z

67.

68.

Z Z

√ dx dx x2 ± a2 1 a √ √ = a arccos |x| , a > 0, =∓ , 63. a2 x x x2 − a2 x2 x2 ± a2 √ Z p x2 ± a2 x dx (x2 + a2 )3/2 √ 65. = x2 ± a2 , 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 2ax + b p 2 4ax − b2 dx √ ax2 + bx + c dx = ax + bx + c + , 2 4a 8a ax + bx + c Z

√

ax2

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

72. 73. 74. 75. 76.

Z

Z

Z

Z

Z

Z

x dx √ = 2 ax + bx + c

Z

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

x cos(ax) dx = xn eax dx =

1 n ax

xn eax − a

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

sin(ax) − n a



Z

n a

n a

Z

Z

xn−1 cos(ax) dx,

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

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

f (x)δx =

a

Differences: ∆(cu) = c∆u,

b−1 X

f (i).

i=a

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

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

∆(2x ) = 2x ,

x x ∆ m = m−1 .

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, P −1 n+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−1

x

x = 1,

1 , (x + 1) · · · (x + |n|) xn+m = xm (x − m)n . Rising Factorial Powers:

sin(ax) dx,

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

n+1

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



Z

x1 = x2 =

x1 x2 + x1

= =

x3 = x4 =

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

= =

x5 =

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

=

x1 = x2 =

x1 x + x1

x1 = x2 =

x3 = x4 =

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

x3 = x4 =

x5 =

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

x5 =

n > 0,

0

xn =

xn−1 eax dx,

2

Finite Calculus

n < 0,

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

n > 0,

x0 = 1,

,

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

x1 x2 − x1

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

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

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

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

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 xn = x = (−1)n−k xk , 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 ′′ f (a) + · · · = f (i) (a). f (x) = f (a) + (x − a)f (a) + 2 i! i=0 Expansions: ∞ X 1 xi , = 1 + x + x2 + x3 + x4 + · · · = 1−x i=0 ∞ X 1 ci xi , = 1 + cx + c2 x2 + c3 x3 + · · · = 1 − cx i=0 ∞ X 1 n 2n 3n xni , = 1 + x + x + x + · · · = 1 − xn i=0 ∞ X x 2 3 4 ixi , = x + 2x + 3x + 4x + · · · = (1 − x)2 i=0 n   ∞ X X n k!z k n 2 n 3 n 4 in xi , = x + 2 x + 3 x + 4 x + · · · = k (1 − z)k+1 i=0 k=0 ∞ X xi = ex = 1 + x + 21 x2 + 16 x3 + · · · , i! i=0 ∞ X xi (−1)i+1 , = ln(1 + x) = x − 12 x2 + 31 x3 − 41 x4 − · · · i i=1 ∞ i Xx 1 ln = x + 21 x2 + 31 x3 + 41 x4 + · · · , = 1−x i i=1 ∞ X x2i+1 1 3 1 5 1 7 sin x = x − 3! , (−1)i x + 5! x − 7! x + ··· = (2i + 1)! i=0 ∞ X x2i 1 4 1 6 1 2 (−1)i x + 4! x − 6! x + ··· = cos x = 1 − 2! , (2i)! i=0 ∞ X x2i+1 (−1)i , = tan−1 x = x − 31 x3 + 51 x5 − 71 x7 + · · · (2i + 1) i=0 ∞   X n i 2 (1 + x)n = 1 + nx + n(n−1) x, x + · · · = 2 i i=0  ∞  X
1 i+n i n+2 2 x, = 1 + (n + 1)x + 2 x + · · · = i (1 − x)n+1 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 √ 1 1 2i i 2 3 = x, (1 − 1 − 4x) = 1 + x + 2x + 5x + · · · 2x i+1 i i=0 ∞   X 1 2i i √ x, = 1 + 2x + 6x2 + 20x3 + · · · = i 1 − 4x i=0 √  n  ∞  X
1 − 1 − 4x 2i + n i 1 4+n 2 √ x, = 1 + (2 + n)x + 2 x + · · · = 2x i 1 − 4x i=0 ∞ X 1 1 3 2 11 3 25 4 ln = x + 2 x + 6 x + 12 x + · · · = Hi xi , 1−x 1−x i=1  2 ∞ X 1 Hi−1 xi 1 11 4 ln = 21 x2 + 43 x3 + 24 , x + ··· = 2 1−x i i=2 ∞ X x 2 3 4 Fi xi , = x + x + 2x + 3x + · · · = 1 − x − x2 i=0 ∞ X Fn x 2 3 Fni xi . = F x + F x + F x + · · · = n 2n 3n 1 − (Fn−1 + Fn+1 )x − (−1)n x2 i=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 (x + y)n = x y . k k=0

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

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

xk A(x) =

∞ X

ai−k xi ,

i=k

A(x) −

Pk−1 i=0

i

ai x

xk

A(cx) =

=

∞ X

ai+k xi ,

i=0

∞ X

ci ai xi ,

i=0

A′ (x) =

∞ X

(i + 1)ai+1 xi ,

i=0

xA′ (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 B(x) = A(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  ln

1 1−x

n

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

Escher’s Knot

   −n ∞   X i n+i i 1 xi , = (Hn+i − Hn ) x, = n i x i=0 i=0 ∞   ∞   X X n i i n!xi x n , = x, (e − 1) = i! i n i=0 i=0 ∞   ∞ X X i n!xi (−4)i B2i x2i = , x cot x = , n i! (2i)! i=0 i=0 ∞ ∞ 2i 2i 2i−1 X X 1 i−1 2 (2 − 1)B2i x (−1) = , , ζ(x) = 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) ζ(2n) x sin x √  n 1 − 1 − 4x 2x x

e sin x

=

∞ X S(i)

xi

√ 1−x x  2 arcsin x x 1−

where S(n) =

i=1 2n−1

d|n d,

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

= =

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

s

a

P

=

∞ X i=0

=

∞ X i=0

i!(n + i)!

2

i/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)

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

b

G(x) dF (x) +

a

G(x) dF (x).

b

Z

G(x) dF (x) +

a

a

b


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

a

Z

c

b

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

Z

b

c · G(x) dF (x) =

a

Z

a

b

Z

a

b

Z

b

H(x) dF (x),

a

b

Z

G(x) dF (x) +

a


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

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

b

G(x) dH(x),

a Z b

Z

G(x) dF (x),

a b

F (x) dG(x).

a

If the integrals involved exist, and F possesses a derivative F ′ at every point in [a, b] then Z b Z b G(x) dF (x) = G(x)F ′ (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 21 32 43 54 65 06 10 89 97 78 42 53 64 05 16 20 31 98 79 87

a

Fibonacci Numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . . Definitions: Fi = Fi−1 +Fi−2 ,

F0 i−1

= F1 = 1,

F−i = (−1) Fi ,   Fi = √15 φi − φˆi ,

Cassini’s identity: for i > 0: Fi+1 Fi−1 − Fi2 = (−1)i .

The Fibonacci number system: Every integer n has a unique representation

Additive rule: Fn+k = Fk Fn+1 + Fk−1 Fn ,

n = Fk1 + Fk2 + · · · + Fkm , where ki ≥ ki+1 + 2 for all i, 1 ≤ i < m and km ≥ 2.

Calculation by matrices:    n Fn−2 Fn−1 0 1 = . 1 1 Fn−1 Fn

F2n = Fn Fn+1 + Fn−1 Fn .