6.042/18.062J Mathematics for Computer Science April 8,2005
Srini Devadas and Eric Lehman
Notes for Recitation 16
Problem 1,Find closed-form generating functions for the following sequences,Do not
concern yourself with issues of convergence,
(a) ?2,3,5,0,0,0,0,...?
Solution.
2 + 3x + 5x
2
(b) ?1,1,1,1,1,1,1,...?
Solution.
1
3
1 + x + x
2
+ x +,.,=
1? x
(c) ?1,2,4,8,16,32,64,...?
Solution.
3 1 3
1 + 2x + 4x
2
+ 8x +,.,= (2x)
0
+ (2x) + (2x)
2
+ (2x) +,.,
1
=
x1? 2
(d) ?1,0,1,0,1,0,1,0,...?
Solution.
1
4 6
1 + x
2
+ x + x +,.,=
1? x
2
(e) ?0,0,0,1,1,1,1,1,...?
Solution.
3
x
3 4 5 6 3 3
x + x + x + x +,.,= x (1 + x + x
2
+ x +,..) =
1? x
(f)?1,3,5,7,9,11,...?
2 Recitation 16
Solution,
1
3
1 + x + x
2
+ x +,.,=
1? x
d 1
d
1 + x + x
2
+ x
3
+,.,=
dx dx 1? x
1
2
1 + 2x + 3x
2
+ 4x +,.,=
(1? x)
2
2
2
2 + 4x + 6x
2
+ 8x +,.,=
(1? x)
2
2 1
3
1 + 3x + 5x
2
+ 7x +,.,=
(1? x)
2
1? x
1 + x
=
(1? x)
2
3 Recitation 16
Problem 2,Find a closed-form generating function for the sequence
(t
0
,t
1
,t
2
,...)
where t
n
is the number of different ways to compose a bag of n donuts subject to the
following restrictions,
(a) All the donuts are chocolate and there are at least 3.
Solution.
3
x
1? x
(b) All the donuts are glazed and there are at most 4.
Solution.
1? x
5
1? x
(c) All the donuts are coconut and there are exactly 2.
Solution.
2
x
(d) All the donuts are plain and the number is a multiple of 4.
Solution.
1
1? x
4
(e) The donuts must be chocolate,glazed,coconut,or plan and,
There must be at least 3 are chocolate donuts,
There must be at most 4 glazed,
There must be exactly 2 coconut,
There must be a multiple of 4 plain,
Solution,
x
3
1? x
5 5 3
1 x (1 + x
2
+ x + x
4
)
2
x =
1? x 1? x 1? x
4
(1? x)(1? x
4
)
4 Recitation 16
Problem 3,[20 points] A previous problem set introduced us to the Catalan numbers,
C
0
,C
1
,C
2
,...,where the n-th of them equals the number of balanced strings that can be
built with 2n paretheses,Here is a list of the?rst several of them,
n 0 1 2 3 4 5 6 7 8 9 10 11 12
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 C
n
Then,in lecture we were all amazed to see that the decimal expansion of the irrational
number 500000?1000
√
249999
1.000001000002000005000014000042000132000429001430004862016796058786208012,.,
“encodes” these numbers! Now,there are many reasons why one may want to turn to
religion,but this revelation is probably not a good one,Let’s explain why,
(a) Let p
n
be the number of balanced strings containing n (’s,Explain why the fol-
lowing recurrence holds,
p
0
= 1, (the empty string)
n
p
n
= p
k?1
·p
n?k
,for n ≥ 1,
k=1
Solution,Note that every nonempty balanced string consists of a sequence of one
or more balanced strings,The?rst balanced string in the sequence must begin with
a ( and end with a,matching” ),That is,any balanced string,r
n
,with n ≥ 1 (’s
consists of a balanced string,s
k?1
,enclosed in brackets and containing k? 1 (’s,
followed by a balanced string,t
n?k
,with n?k (’s,
r
n
= (s
k?1
) followed by t
n?k
where 1 ≤ k ≤ n,This observation leads directly to the recurrence,
(b) Now consider the generating function for the number of balanced strings,
3
P(x) = p
0
+ p
1
x + p
2
x
2
+ p
3
x + ···,
Prove that
P(x) = xP(x)
2
+ 1,
Solution,We can verify this equation using the recurrence relation,
xP(x)
2
+ 1 = x(p
0
+ p
1
x + p
2
x
2
+ p
3
x
3
+ ···)
2
+ 1
= x(p
2
0
+ (p
0
p
1
+ p
1
p
0
)x + (p
0
p
2
+ p
1
p
1
+ p
2
p
0
)x
2
+ ···) + 1
= 1 + p
2
0
x + (p
0
p
1
+ p
1
p
0
)x
2
+ (p
0
p
2
+ p
1
p
1
+ p
2
p
0
)x
3
+ ···
= 1 + p
1
x + p
2
x
2
+ p
3
x
3
+ ···
= P(x)
5 Recitation 16
(c) Find a closed-form expression for the generating function P(x),
Solution,Given that P(x) = xP (x)
2
+ 1,the quadratic formula implies that
1 ±
√
1?4x
P(x) =,
2x
If x is small,then P(x) should be about p
0
= 1,Therefore,the correct choice of sign
is
1?
√
1?4x
P(x) = ,
2x
(d) Show that P(1/1000000) = 500000?1000
√
249999,
Solution,
P(1/1000000) =
1? 1?4/1000000
2/1000000
249999
= 500000?500000
250000
= 500000?1000
√
249999
(e) Explain why the digits of this irrational number encode these successive numbers
of balanced strings,
Solution,Suppose that we symbolically carry out the substitution done in the pre-
ceding problem part,
3
P(x) = p
0
+ p
1
x + p
2
x
2
+ p
3
x + ···
P(10
6
) = p
0
+ p
1
10
6
+ p
2
10
12
+ p
3
10
18
+ ···
Thus,p
0
appears in the units position,p
1
appears in the millionths position,p
2
ap-
pears in the trillionths position,and so forth,
?
?
6 Recitation 16
Problem 4,Consider the following recurrence equation,
1 n = 0
T
n
= 2 n = 1
2T
n?1
+ 3T
n?2
(n ≥ 2)
Let f(x) be a generating function for the sequence?T
0
,T
1
,T
2
,T
3
,...?,
(a) Give a generating function in terms of f(x) for the sequence,
,2,2T
1
+ 3T
0
,2T
2
+ 3T
1
,2T
3
+ 3T
2
,...1
Solution,We can break this down into a linear combination of three sequences,
1,2,0,0,0,..,= 1 + 2x
0,T
0
,T
1
,T
2
,T
3
,..,= xf(x)
0,0,T
0
,T
1
,T
2
,..,? = x
2
f(x)
In particular,the sequence we want is very nearly generated by 1 + 2x + 2xf(x) +
3x
2
f(x),However,the second term is not quite correct; we’re generating 2+2T
0
= 4
instead of the correct value,which is 2,We correct this by subtracting 2x from the
generating function,which leaves,
1 + 2xf(x) + 3x
2
f(x)
(b) Form an equation in f(x) and solve to obtain a closed-form generating function
for f(x),
Solution,The equation
f(x) = 1 + 2xf(x) + 3x
2
f(x)
equates the left sides of all the equations de?ning the sequence T
0
,T
1
,T
2
,..,with all
the right sides,Solving for f(x) gives the closed-form generating function,
1
f(x) =
1? 2x? 3
2
x
(c) Expand the closed form for f(x) using partial fractions.
Solution,We can write:
1? 2x? 3
2
x = (1 + x)(1? 3x)
Thus,there exist constants A and B such that:
1 A B
f(x) = = +
1? 2x? 3x
2
1 + x 1? 3x
7 Recitation 16
Now substituting x = 0 and x = 1 gives the system of equations,
1 = A + B
1 A B
=?
4 2
2
Solving the system,we?nd that A = 1/4 and B = 3/4,Therefore,we have,
1/4 3/4
f(x) = +
1 + x 1? 3x
(d) Find a closed-form expression for T
n
from the partial fractions expansion,
Solution,Using the formula for the sum of an in?nite geometric series gives,
1
3
?
1? x + x
2 3 4 2 3 4 4
f(x) =
4
x + x?,.,+
4
1 + 3x + 3 x
2
+ 3 x
3
+ 3 x +,.,
Thus,the coef?cient of x
n
is,
1 3
3
n
T
n
=
4
· (?1)
n
+
4
·
Srini Devadas and Eric Lehman
Notes for Recitation 16
Problem 1,Find closed-form generating functions for the following sequences,Do not
concern yourself with issues of convergence,
(a) ?2,3,5,0,0,0,0,...?
Solution.
2 + 3x + 5x
2
(b) ?1,1,1,1,1,1,1,...?
Solution.
1
3
1 + x + x
2
+ x +,.,=
1? x
(c) ?1,2,4,8,16,32,64,...?
Solution.
3 1 3
1 + 2x + 4x
2
+ 8x +,.,= (2x)
0
+ (2x) + (2x)
2
+ (2x) +,.,
1
=
x1? 2
(d) ?1,0,1,0,1,0,1,0,...?
Solution.
1
4 6
1 + x
2
+ x + x +,.,=
1? x
2
(e) ?0,0,0,1,1,1,1,1,...?
Solution.
3
x
3 4 5 6 3 3
x + x + x + x +,.,= x (1 + x + x
2
+ x +,..) =
1? x
(f)?1,3,5,7,9,11,...?
2 Recitation 16
Solution,
1
3
1 + x + x
2
+ x +,.,=
1? x
d 1
d
1 + x + x
2
+ x
3
+,.,=
dx dx 1? x
1
2
1 + 2x + 3x
2
+ 4x +,.,=
(1? x)
2
2
2
2 + 4x + 6x
2
+ 8x +,.,=
(1? x)
2
2 1
3
1 + 3x + 5x
2
+ 7x +,.,=
(1? x)
2
1? x
1 + x
=
(1? x)
2
3 Recitation 16
Problem 2,Find a closed-form generating function for the sequence
(t
0
,t
1
,t
2
,...)
where t
n
is the number of different ways to compose a bag of n donuts subject to the
following restrictions,
(a) All the donuts are chocolate and there are at least 3.
Solution.
3
x
1? x
(b) All the donuts are glazed and there are at most 4.
Solution.
1? x
5
1? x
(c) All the donuts are coconut and there are exactly 2.
Solution.
2
x
(d) All the donuts are plain and the number is a multiple of 4.
Solution.
1
1? x
4
(e) The donuts must be chocolate,glazed,coconut,or plan and,
There must be at least 3 are chocolate donuts,
There must be at most 4 glazed,
There must be exactly 2 coconut,
There must be a multiple of 4 plain,
Solution,
x
3
1? x
5 5 3
1 x (1 + x
2
+ x + x
4
)
2
x =
1? x 1? x 1? x
4
(1? x)(1? x
4
)
4 Recitation 16
Problem 3,[20 points] A previous problem set introduced us to the Catalan numbers,
C
0
,C
1
,C
2
,...,where the n-th of them equals the number of balanced strings that can be
built with 2n paretheses,Here is a list of the?rst several of them,
n 0 1 2 3 4 5 6 7 8 9 10 11 12
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 C
n
Then,in lecture we were all amazed to see that the decimal expansion of the irrational
number 500000?1000
√
249999
1.000001000002000005000014000042000132000429001430004862016796058786208012,.,
“encodes” these numbers! Now,there are many reasons why one may want to turn to
religion,but this revelation is probably not a good one,Let’s explain why,
(a) Let p
n
be the number of balanced strings containing n (’s,Explain why the fol-
lowing recurrence holds,
p
0
= 1, (the empty string)
n
p
n
= p
k?1
·p
n?k
,for n ≥ 1,
k=1
Solution,Note that every nonempty balanced string consists of a sequence of one
or more balanced strings,The?rst balanced string in the sequence must begin with
a ( and end with a,matching” ),That is,any balanced string,r
n
,with n ≥ 1 (’s
consists of a balanced string,s
k?1
,enclosed in brackets and containing k? 1 (’s,
followed by a balanced string,t
n?k
,with n?k (’s,
r
n
= (s
k?1
) followed by t
n?k
where 1 ≤ k ≤ n,This observation leads directly to the recurrence,
(b) Now consider the generating function for the number of balanced strings,
3
P(x) = p
0
+ p
1
x + p
2
x
2
+ p
3
x + ···,
Prove that
P(x) = xP(x)
2
+ 1,
Solution,We can verify this equation using the recurrence relation,
xP(x)
2
+ 1 = x(p
0
+ p
1
x + p
2
x
2
+ p
3
x
3
+ ···)
2
+ 1
= x(p
2
0
+ (p
0
p
1
+ p
1
p
0
)x + (p
0
p
2
+ p
1
p
1
+ p
2
p
0
)x
2
+ ···) + 1
= 1 + p
2
0
x + (p
0
p
1
+ p
1
p
0
)x
2
+ (p
0
p
2
+ p
1
p
1
+ p
2
p
0
)x
3
+ ···
= 1 + p
1
x + p
2
x
2
+ p
3
x
3
+ ···
= P(x)
5 Recitation 16
(c) Find a closed-form expression for the generating function P(x),
Solution,Given that P(x) = xP (x)
2
+ 1,the quadratic formula implies that
1 ±
√
1?4x
P(x) =,
2x
If x is small,then P(x) should be about p
0
= 1,Therefore,the correct choice of sign
is
1?
√
1?4x
P(x) = ,
2x
(d) Show that P(1/1000000) = 500000?1000
√
249999,
Solution,
P(1/1000000) =
1? 1?4/1000000
2/1000000
249999
= 500000?500000
250000
= 500000?1000
√
249999
(e) Explain why the digits of this irrational number encode these successive numbers
of balanced strings,
Solution,Suppose that we symbolically carry out the substitution done in the pre-
ceding problem part,
3
P(x) = p
0
+ p
1
x + p
2
x
2
+ p
3
x + ···
P(10
6
) = p
0
+ p
1
10
6
+ p
2
10
12
+ p
3
10
18
+ ···
Thus,p
0
appears in the units position,p
1
appears in the millionths position,p
2
ap-
pears in the trillionths position,and so forth,
?
?
6 Recitation 16
Problem 4,Consider the following recurrence equation,
1 n = 0
T
n
= 2 n = 1
2T
n?1
+ 3T
n?2
(n ≥ 2)
Let f(x) be a generating function for the sequence?T
0
,T
1
,T
2
,T
3
,...?,
(a) Give a generating function in terms of f(x) for the sequence,
,2,2T
1
+ 3T
0
,2T
2
+ 3T
1
,2T
3
+ 3T
2
,...1
Solution,We can break this down into a linear combination of three sequences,
1,2,0,0,0,..,= 1 + 2x
0,T
0
,T
1
,T
2
,T
3
,..,= xf(x)
0,0,T
0
,T
1
,T
2
,..,? = x
2
f(x)
In particular,the sequence we want is very nearly generated by 1 + 2x + 2xf(x) +
3x
2
f(x),However,the second term is not quite correct; we’re generating 2+2T
0
= 4
instead of the correct value,which is 2,We correct this by subtracting 2x from the
generating function,which leaves,
1 + 2xf(x) + 3x
2
f(x)
(b) Form an equation in f(x) and solve to obtain a closed-form generating function
for f(x),
Solution,The equation
f(x) = 1 + 2xf(x) + 3x
2
f(x)
equates the left sides of all the equations de?ning the sequence T
0
,T
1
,T
2
,..,with all
the right sides,Solving for f(x) gives the closed-form generating function,
1
f(x) =
1? 2x? 3
2
x
(c) Expand the closed form for f(x) using partial fractions.
Solution,We can write:
1? 2x? 3
2
x = (1 + x)(1? 3x)
Thus,there exist constants A and B such that:
1 A B
f(x) = = +
1? 2x? 3x
2
1 + x 1? 3x
7 Recitation 16
Now substituting x = 0 and x = 1 gives the system of equations,
1 = A + B
1 A B
=?
4 2
2
Solving the system,we?nd that A = 1/4 and B = 3/4,Therefore,we have,
1/4 3/4
f(x) = +
1 + x 1? 3x
(d) Find a closed-form expression for T
n
from the partial fractions expansion,
Solution,Using the formula for the sum of an in?nite geometric series gives,
1
3
?
1? x + x
2 3 4 2 3 4 4
f(x) =
4
x + x?,.,+
4
1 + 3x + 3 x
2
+ 3 x
3
+ 3 x +,.,
Thus,the coef?cient of x
n
is,
1 3
3
n
T
n
=
4
· (?1)
n
+
4
·
