Theoretical Computer Science Cheat Sheet
Identities Cont. Trees
38.
n +1
m +1
=
k
n
k

k
m
=
n
k=0
k
m
n
n−k
= n!
n
k=0
1
k!
k
m
, 39.
x
x − n
=
n
k=0
n
k

x + k
2n
,
40.
n
m
=
k
n
k

k +1
m +1
(−1)
n−k
, 41.
n
m
=
k
n +1
k +1

k
m
(−1)
m−k
,
42.
m + n +1
m
=
m
k=0
k
n + k
k
, 43.
m + n +1
m
=
m
k=0
k(n + k)
n + k
k
,
44.
n
m
=
k
n +1
k +1

k
m
(−1)
m−k
, 45. (n − m)!
n
m
=
k
n +1
k +1

k
m
(−1)
m−k
, for n ≥ m,
46.
n
n − m
=
k
m − n
m + k

m + n
n + k

m + k
k
, 47.
n
n − m
=
k
m − n
m + k

m + n
n + k

m + k
k
,
48.
n
+ m

+ m
=
k
k

n − k
m

n
k
, 49.
n
+ m

+ m
=
k
k

n − k
m

n
k
.
Every tree with n
vertices has n − 1
edges.
Kraft inequal-
ity: If the depths
of the leaves of
a binary tree are
d
1
,...,d
n
:
n
i=1
2
−d
i
≤ 1,
and equality holds
only if every in-
ternal node has 2
sons.
Recurrences
Master method:
T (n)=aT (n/b)+f (n),a≥ 1,b > 1
If ∃>0 such that f(n)=O(n
log
b
a−
)
then
T (n)=Θ(n
log
b
a
).
If f(n)=Θ(n
log
b
a
) then
T (n)=Θ(n
log
b
a
log
2
n).
If ∃>0 such that f(n)=Ω(n
log
b
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
T
i+1
=2
2
i
· T
2
i
,T
1
=2.
Note that T
i
is always a power of two.
Let t
i
= log
2
T
i
. Then we have
t
i+1
=2
i
+2t
i
,t
1
=1.
Let u
i
= t
i
/2
i
. Dividing both sides of
the previous equation by 2
i+1
we get
t
i+1
2
i+1
=
2
i
2
i+1
+
t
i
2
i
.
Substituting we find
u
i+1
=
1
2
+ u
i
,u
1
=
1
2
,
which is simply u
i
= i/2. So we find
that T
i
has the closed form T
i
=2
i2
i−1
.
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 “tele-
scope”
1
T (n) −3T (n/2) = n
3
T (n/2) −3T (n/4) = n/2
.
.
.
.
.
.
.
.
.
3
log
2
n−1
T (2) −3T (1) = 2
Let m = log
2
n. Summing the left side
we get T (n) − 3
m
T (1) = T (n) − 3
m
=
T (n) − n
k
where k = log
2
3 ≈ 1.58496.
Summing the right side we get
m−1
i=0
n
2
i
3
i
= n
m−1
i=0
3
2
i
.
Let c =
3
2
. Then we have
n
m−1
i=0
c
i
= n
c
m
− 1
c − 1
=2n(c
log
2
n
− 1)
=2n(c
(k−1) log
c
n
− 1)
=2n
k
− 2n,
and so T (n)=3n
k
− 2n. Full history re-
currences can often be changed to limited
history ones (example): Consider
T
i
=1+
i−1
j=0
T
j
,T
0
=1.
Note that
T
i+1
=1+
i
j=0
T
j
.
Subtracting we find
T
i+1
− T
i
=1+
i
j=0
T
j
− 1 −
i−1
j=0
T
j
= T
i
.
And so T
i+1
=2T
i
=2
i+1
.
Generating functions:
1. Multiply both sides of the equa-
tion by x
i
.
2. Sum both sides over all i for
which the equation is valid.
3. Choose a generating function
G(x). Usually G(x)=
∞
i=0
x
i
g
i
.
3. Rewrite the equation in terms of
the generating function G(x).
4. Solve for G(x).
5. The coefficient of x
i
in G(x)isg
i
.
Example:
g
i+1
=2g
i
+1,g
0
=0.
Multiply and sum:
i≥0
g
i+1
x
i
=
i≥0
2g
i
x
i
+
i≥0
x
i
.
We choose G(x)=
i≥0
x
i
g
i
. Rewrite
in terms of G(x):
G(x) − g
0
x
=2G(x)+
i≥0
x
i
.
Simplify:
G(x)
x
=2G(x)+
1
1 − x
.
Solve for G(x):
G(x)=
x
(1 − x)(1 − 2x)
.
Expand this using partial fractions:
G(x)=x
2
1 − 2x
−
1
1 − x
= x
2
i≥0
2
i
x
i
−
i≥0
x
i
=
i≥0
(2
i+1
− 1)x
i+1
.
So g
i
=2
i
− 1.