Theoretical Computer Science Cheat Sheet
Series Escher’s Knot
Expansions:
1
(1 − x)
n+1
ln
1
1 − x
=
∞
i=0
(H
n+i
− H
n
)
n + i
i
x
i
,
1
x
−n
=
∞
i=0
i
n
x
i
,
x
n
=
∞
i=0
n
i
x
i
, (e
x
− 1)
n
=
∞
i=0
i
n
n!x
i
i!
,
ln
1
1 − x
n
=
∞
i=0
i
n
n!x
i
i!
,xcot x =
∞
i=0
(−4)
i
B
2i
x
2i
(2i)!
,
tan x =
∞
i=1
(−1)
i−1
2
2i
(2
2i
− 1)B
2i
x
2i−1
(2i)!
,ζ(x)=
∞
i=1
1
i
x
,
1
ζ(x)
=
∞
i=1
µ(i)
i
x
,
ζ(x − 1)
ζ(x)
=
∞
i=1
φ(i)
i
x
,
Stieltjes Integration
ζ(x)=
p
1
1 − p
−x
,
ζ
2
(x)=
∞
i=1
d(i)
x
i
where d(n)=
d|n
1,
ζ(x)ζ(x −1) =
∞
i=1
S(i)
x
i
where S(n)=
d|n
d,
ζ(2n)=
2
2n−1
|B
2n
|
(2n)!
π
2n
,n∈ N,
x
sin x
=
∞
i=0
(−1)
i−1
(4
i
− 2)B
2i
x
2i
(2i)!
,
1 −
√
1 − 4x
2x
n
=
∞
i=0
n(2i + n − 1)!
i!(n + i)!
x
i
,
e
x
sin x =
∞
i=1
2
i/2
sin
iπ
4
i!
x
i
,
1 −
√
1 − x
x
=
∞
i=0
(4i)!
16
i
√
2(2i)!(2i + 1)!
x
i
,
arcsin x
x
2
=
∞
i=0
4
i
i!
2
(i + 1)(2i + 1)!
x
2i
.
If G is continuous in the interval [a, b] and F is nondecreasing then
b
a
G(x) dF (x)
exists. If a ≤ b ≤ c then
c
a
G(x) dF (x)=
b
a
G(x) dF (x)+
c
b
G(x) dF (x).
If the integrals involved exist
b
a
G(x)+H(x)
dF (x)=
b
a
G(x) dF (x)+
b
a
H(x) dF(x),
b
a
G(x) d
F (x)+H(x)
=
b
a
G(x) dF (x)+
b
a
G(x) dH(x),
b
a
c · G(x) dF (x)=
b
a
G(x) d
c · F (x)
= c
b
a
G(x) dF (x),
b
a
G(x) dF (x)=G(b)F (b) − G(a)F (a) −
b
a
F (x) dG(x).
If the integrals involved exist, and F possesses a derivative F
at every
point in [a, b] then
b
a
G(x) dF (x)=
b
a
G(x)F
(x) dx.
Cramer’s Rule
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
Fibonacci Numbers
If we have equations:
a
1,1
x
1
+ a
1,2
x
2
+ ···+ a
1,n
x
n
= b
1
a
2,1
x
1
+ a
2,2
x
2
+ ···+ a
2,n
x
n
= b
2
.
.
.
.
.
.
.
.
.
a
n,1
x
1
+ a
n,2
x
2
+ ···+ a
n,n
x
n
= b
n
Let A =(a
i,j
) and B be the column matrix (b
i
). Then
there is a unique solution iff det A = 0. Let A
i
be A
with column i replaced by B. Then
x
i
=
det A
i
det A
.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...
Definitions:
F
i
= F
i−1
+F
i−2
,F
0
= F
1
=1,
F
−i
=(−1)
i−1
F
i
,
F
i
=
1
√
5
φ
i
−
ˆ
φ
i
,
Cassini’s identity: for i>0:
F
i+1
F
i−1
− F
2
i
=(−1)
i
.
Additive rule:
F
n+k
= F
k
F
n+1
+ F
k−1
F
n
,
F
2n
= F
n
F
n+1
+ F
n−1
F
n
.
Calculation by matrices:
F
n−2
F
n−1
F
n−1
F
n
=
01
11
n
.
The Fibonacci number system:
Every integer n has a unique
representation
n = F
k
1
+ F
k
2
+ ···+ F
k
m
,
where k
i
≥ k
i+1
+ 2 for all i,
1 ≤ i<mand k
m
≥ 2.
Improvement makes strait roads, but the crooked
roads without Improvement, are roads of Genius.
– William Blake (The Marriage of Heaven and Hell)