Math 340 Tutorial 3 Solutions
1. Use generating functions to find a closed formula for the following sums:
(a) nk=0 k.
(b) nk=0(k + 1)2.
(c) nk=0 2k. Solution:
(a) Let an = nk=0 k. Then an = an−1 + n, with a0 = 0. We can solve this recurrence using generating functions. Let A(x) = n≥0 anxn. Let’s write the first few terms in the recurrence:
a1 = a0 + 1 a2 = a1 + 2 a3 = a2 + 3 a4 = a3 + 4 a5 = a4 + 5
.
Now we will multiply each equation by a power of x like so:
a1x = a0x + x a2x2 = a1x2 + 2×2 a3x3 = a2x3 + 3×3 a4x4 = a3x4 + 4×4 a5x5 = a4x5 + 5×5
.
If we add these equations together, then the sum on the left hand side is a1x+a2x2 +a3x3 +a4x4 +a5x5 +···=A(x)−a0 =A(x),
and the right hand side is
a0x+a1x2 +a2x3 +a3x4 +a4x5 +…+x+2×2 +3×3 +4×4 +5×5 +…
= xA(x) + B(x)
where B(x) is the generating function that corresponds to the sequence 0, 1, 2, 3, 4, 5, . . . .
This sequence can be found by taking the derivative of 1 , then multiplying by 1−x
x . NowwecansolveforA(x): (1−x)2
x. SoB(x)=
So we have A(x), but our ultimate goal is to solve for an. an is the coefficient of
xn in A(x), so we just need to figure out the coefficients of A(x). Starting from
1 , taking the derivative twice gives us 2 . Then we divide by 2 and multiply 1−x (1−x)3
by x to get x . The corresponding sequence is: (1−x)3
A(x) = xA(x) + (1 − x)A(x) = x
x (1−x)2
(1−x)2 A(x) = x
.
(1−x)3
0, 1 · 2 , 2 · 3 , 3 · 4 , 4 · 5 , . . . , n(n + 1) , . . . 2222 2
Hence, an = n(n+1) . 2
(a) continued:
(b) Let an = nk=0(k+1)2. Then an = an−1 +(n+1)2, with a0 = 1. Letting A(x) = n≥0 anxn, by the same method as before, we get
A(x) − 1 = xA(x) + B(x),
where B(x) corresponds to the sequence 0, 22, 32, 42, 52, 62, . . . . To get this se-
quence, we first take the derivative of 1 twice to get 2 , which corresponds 1−x (1−x)3
to the sequence 1 · 2,2 · 3,3 · 4,4 · 5,…,(n + 1)(n + 2),…. This is close, but
we need to subtract (n + 1) from each of these terms to get (n + 1)2. Hence,
we need to subtract the sequence 1,2,3,4,5,6,…,(n+1),…, and we know this
corresponds to 1 . So 2 − 1 gives us 12,22,32,42,…. Subtracting 1 (1−x)2 (1−x)3 (1−x)2
gives us the sequence for B(x). Hence,
B(x) = 2 − 1 − 1 = 2 − (1 − x) − 1 =
2 + x (1−x)3
− 1.
(1−x)3 (1−x)2 (1−x)3 Now we can solve for A(x):
A(x)−1=xA(x)+ 1+x −1 (1−x)3
(1−x)A(x) = 1+x (1−x)3
A(x)= 1+x (1−x)4
So we need for figure out the sequence that corresponds to x+x2 . We should (1−x)4
reallythinkofthisas 1 + x . Now 6 isthethirdderivativeof 1 , (1−x)4 (1−x)4 (1−x)4 1−x
which corresponds to 1 · 2 · 3,2 · 3 · 4,…,(n + 1)(n + 2)(n + 3),…, but we need
to divide this by 6. Lastly, we need to multiply by x for the second term to get
x , corresponding to 0,1·2·3/6,2·3·4/6,…,n(n+1)(n+2)/6,…. Putting (1−x)4
this all together, we get
an = n(n+1)(n+2)+(n+1)(n+2)(n+3) 6
= (n+1)(n+2)(2n+3). 6
(b) continued:
(c) Same strategy as before. We have
A(x) − 1 = xA(x) + B(x)
where B(x) corresponds to the sequence 0, 21, 22, 23, 24, . . . , 2n, . . . . We know that 1 corresponds to 20, 21, 22, 23, 24, . . . . So we just need to subtract 1 to get B(x).
1 − 1 1−2x
1−x 1−2x
Hence, an = −1 + 2(2n). Notice that this is equal to 1−2n+1 , which agrees with 1−2
the geometric formula.
1−2x
Now we can solve for A(x):
A(x) − 1 = xA(x) + (1 − x)A(x) = 1
1−2x A(x) = 1
(1−x)(1−2x) = −1 + 2 .
2. Solve the following recurrences using generating functions:
(a) a0 =1,a1 =1,an =2an−1 −an−2. (b) a0 =1,a1 =6,an =3an−1 −2an−2.
(c) a0 =1,a1 =2,a2 =3,an =3an−1 −3an−2 +an−3. (d) a0 =1,a1 =2,an =2an−1 −an−2 +n.
Solution:
(a) Let A(x) = n≥0 anxn. Just like we did in question 1, we will write out a bunch of the equations in the recurrence like so:
a2 = 2a1 − a0 a3 = 2a2 − a1 a4 = 2a3 − a2 a5 = 2a4 − a3
.
Now multiply be an appropriate power of x like so:
a2x2 = 2a1x2 − a0x2 a3x3 = 2a2x3 − a1x3 a4x4 = 2a3x4 − a2x4 a5x5 = 2a4x5 − a3x5
.
If we add these equations together, we have the following equation: A(x) − a1x − a0 = 2xA(x) − a0 − x2A(x).
We know a0 = 1 and a1 = 1, so let’s plug those values in: A(x) − x − 1 = 2xA(x) − 1 − x2A(x).
Now solve for A(x):
A(x) = 1 − x . 1−2x+x2
1−2x+x2 =(1−x)2,sowehave
A(x)= 1−x = 1 . (1−x)2 1−x
Soasitturnsout,an =1foralln.
(a) continued:
(b) Using the same strategy as before, we get
A(x) − a1x − a0 = 3xA(x) − a0 − 2x2A(x).
Pluggingina1 =6anda0 =1gives
A(x) − 6x − 1 = 3xA(x) − 1 − 2x2A(x).
Solving for A(x) gives
A(x) = 3x + 1 = 3x + 1 .
Now we can split
So
Hence, an = 5(2n) − 4.
1−3x+2×2 (1−x)(1−2x)
3x+1 using partial fractions. We end up with
(1−x)(1−2x) 1−x 1−2x
A(x)= −4 − 5 . 1−2x 1−x
(1−x)(1−2x)
3x+1 =−4+5.
(b) continued:
(c) Because this is a 3 step recurrence and not a 2 step, we’ll derive the formula for A(x) again:
a3 =3a2 −3a1 +a0 a4 =3a3 −3a2 +a1 a5 =3a4 −3a3 +a2 a6 =3a5 −3a4 +a3 a7 =3a6 −3a5 +a4
.
Now multiply by the appropriate powers of x like so:
a3x3 = 3a2x3 − 3a1x3 + a0x3 a4x4 = 3a3x4 − 3a2x4 + a1x4 a5x5 = 3a4x5 − 3a3x5 + a2x5 a6x6 = 3a5x6 − 3a4x6 + a3x6 a7x7 = 3a6x7 − 3a5x7 + a4x7
.
Adding the equations together, we get
A(x)−a x2 −a x−a =3xA(x)−a x−a −3×2A(x)−a +x3A(x).
210100 Plugging in a0 = 1, a1 = 2, a2 = 3, we get
A(x)−3×2 −2x−1=3xA(x)−2x−1−3×2A(x)−1+x3A(x). Solving for A(x) gives us
A(x)= 1−x = 1−x = 1 . 1−3x+3×2 −x3 (1−x)3 (1−x)2
Since 1 corresponds to the sequence 1, 2, 3, 4, 5, . . . , it follows that a (1−x)2
n
= n+1.
(c) continued:
(d) Now we have an inhomogeneous factor in our recurrence. Not to worry though, as we can perform the exact same steps as before:
a2 = 2a1 − a0 + 2 a3 = 2a2 − a1 + 3 a4 = 2a3 − a2 + 4 a5 = 2a4 − a3 + 5 a6 = 2a5 − a4 + 6
. Multiply by the appropriate powers of x:
a2x2 = 2a1x2 − a0x2 + 2×2 a3x3 = 2a2x3 − a1x3 + 3×3 a4x4 = 2a3x4 − a2x4 + 4×4 a5x5 = 2a4x5 − a3x5 + 5×5 a6x6 = 2a5x6 − a4x6 + 6×6
.
Adding the equations together gives
A(x)−a x−a =2xA(x)−a −x2A(x)+B(x),
100
where B(x) corresponds to the sequence 0, 0, 2, 3, 4, 5, 6, dots. To get here, we take the derivative of 1 , subtract 1, and multiply by x. So
1−x
A(x)−a1x−a0 =2x A(x)−a0 −x A(x)+x (1−x)2 −1 .
21
Nowplugina0 =1,a1 =2:
A(x)−2x−1=2x A(x)−1 −x A(x)+x (1−x)2 −1 .
21
Solve for A(x):
1x1 A(x)=1−2x+x2 +1−2x+x2 (1−x)2 −1
=1+x−x (1−x)2 (1−x)4 (1−x)2
=1+x. 1−x (1−x)4
x is found by taking the derivative of 1 3 times to get 6 , then multi- (1−x)4 1−x (1−x)4
plying by x/6. So the corresponding sequence is 0,1·2·3/6,2·3·4/6,…,n(n+1)(n+2)/6,…
Therefore, an = 1 + n(n+1)(n+2) . 6
(d) continued:
3. Suppose that an = bn−1 + ni=1 an−i for some sequence bn. Show that an = 2an−1 + bn−1−bn−2 forn≥2.
Hint: this fact will be useful for problems 4 (b) and 5(b).
Solution
Observe that
nn
an −an−1 =bn−1 +an−i −(bn−2 +an−1−i)
i=1 i=1 n−1
n
=bn−1 −bn−2 +an−1 +(an−i −an−1−i)=an−1 +bn−1 −bn−2,
i=2 i=1 and so an = 2an−1 + bn−1 − bn−2 as desired.
4. Tilings
(a) Let gn be the number of ways to cover a 1×n board using only 1×1 red tiles, 1 × 1 blue tiles, and 1 × 2 yellow tiles. Find a recurrence for gn and solve this recurrence using generating functions.
(b) A tromino consists of 3 connected unit squares, i.e. the shapes and along with their rotations. How many ways are there to tile a 2 × n unit rectangle with trominoes?
Solution to 4a: Suppose we have an empty 1 × n board and we start filling it with tiles. How many ways can we fill the left most tile? We could use any of the 3 tiles. If we use either of the 1×1 tiles, we are left to fill in a 1×n−1 board, and if we use the 1×2 tiles, we are left to fill in a 1×n−2 board. The number of ways to fill the 1 × n board is just the sum over all 3 cases of the number of ways to fill the remaining board. Hence,
gn = 2gn−1 + gn−2.
For the base cases, g0 = 1 (1 way to do nothing) and g1 = 2, since there are 2 1×1 tiles. Now we can solve this recurrence using generating functions. Let G(x) = n≥0 gnxn. Then 2
G(x)−g1x−g0 =2x G(x)−a0 +x G(x). Puttingg1 =2andg0 =1:
Solving for G(x):
G(x) − 2x − 1 = 2xG(x) − 1 + x2G(x). G(x) = 1
1−2x−x2
= 1−(1+√2)x1−(1−√2)x
2+√2 1 2−√2 1
= 4 1−(1+√2)x + 4 1−(1−√2)x
2+√2 √ 2−√2 √ gn= 4 (1+ 2)n+ 4 (1− 2)n
1
Therefore,
Solution to 4b:
Let Tn be the number of ways to tile a 2 × n board with trominoes.
First, we consider the different ways of starting our tiling. There are 3 cases:
Case 1: The lower left corner of the board is filled with a piece. In this case the top left corner must also be filled with a piece, and so the start of our tiling is . Let Ln be the number of tilings of a 2 × n board that start this way and notice that Ln = Tn−3.
Case 2: The lower left corner is filled with a piece. Notice that the only way to extend this start is to next place 0 up to k pieces followed by a piece. For example, with 0 pieces this position looks like , and with 1 it looks like
. Let An,k be the number of ways to tile a 2×n board that start with a followed by k pieces followed by a piece, and notice that An,k = Tn−3(k+1).
Case 3: The lower left corner is filled with a piece. The case analysis here is the same as in case 2, but with all of the pieces flipped upside down. Let Bn,k be the number of ways to tile a 2 × n board in by starting in the relevant way, and notice that Bn,k = Tn−3(k+1).
With the starting case analysis done, notice that Tn = 0 if n is not a multiple of 3, and otherwise we see that
m−1 m−1
T3m = L3m + (A3m,k + B3m,k) = T3(m−1) + 2T3m−3(k+1).
k=0 k=0
Now, considering T3m − T3(m−1), by the same argument from problem 3 we see that
T3m = 4T3(m−1) − T3(m−2).
Now, to make our lives easier let an = T3n and consider A(x) = anxn. By our usual
tricks we see that
A(x) = a0 + a1x + 4x(A(x) − a0) − x2A(x).
Plugging in the initial conditions a0 = 1 and a1 = 3 and solving for A(x) we get
Using partial fractions:
A(x) = 1 − x . 1−4x+x2
√√ A(x)= 1/6(3+√3 + 1/6(3−√3 .
1−(2+ 3x 1−(2− 3x
Finally, using our formula for the sequence corresponding to c we see 1−αx
an = 1(3+√3)(2+√3)n + 1(3−√3)(2−√3)n. 66
5. Lattice walks
(a) Consider walks on the integer lattice that start from (0, 0) and use steps of the form (1, 0), (0, 1), or (−1, 0) (i.e., from the point (a, b) we can reach any of (a+1, b), (a, b + 1), or (a − 1, b) in a single step). How many length n walks are there? How many length n walks are there that do not intersect themselves?
(b) Consider walks on the integer lattice that start from (0, 0) and use steps of the form (1,0) or (0,a) for a ∈ {1,…,n}. How many such walks end on a point (x,y) such that x + y = n?
Solution to 5a: We partition based off of the last two step.
If the last step was up, then this could have been preceded by any other type of
step, and so there are an−1 ways to end with an up step.
Similarly, note that there are an−1 paths that end in any of left-left, right-right,
or up-left (we take any path of length n − 1 then do the last forced step). Finally, there an−2 walks that end with an up-right move.
As this covers all of the ways to end a walk, we see that an = 2an−1 + an−2. Therefore, letting A(x) = n≥0 anxn and using our standard tricks we see that
A(x) = a0 + a1x + 2x(A(x) − a0) + x2A(x).
Next, plugging in a0 = 1 and a1 = 3 and solving for A(x), we see that
A(x) = 1 + x . 1−2x−x2
Using partial fractions, we find
√√ .5(1+ 2) .5(1− 2
A(x) = √ + √ 1−(1+ 2)x 1−(1− 2)x
So, by our formula for the generating function of c , we have 1−αx
an = 1+√2(1+√2)n + 1−√2(1−√2)n 22
Solution to problem 5b: As usual, we set up our recurrence by partitioning based on the last move. If we end with a (1, 0) move then the second to last point (x, y) in our walk satisfies x + y = n − 1. Similarly, If we end with a (0, a) move then the second to last point (x, y) in our walk satisfies x + y = n − a.
Consequently, we see that an = an−1 + ni=1 an−i. Therefore, by problem 3. we know an = 3an−1 − an−2.
Now, rather than finishing the proof by hand we’ll actually just show that an = F2n, where F2n is the 2n’th Fibonacci number. Since we already know the formula for the Fibonacci numbers from class this will save us some time.
AsweknowF0 =a0 =1andF2 =a1 =3,itsufficestoshowthatF2n = 3F2(n−1 − F2(n−2). To do this we just use the fact that Fn = Fn−1 + Fn−2 twice followed by the fact that F2n−3 = F2n−2 − F2n−4 once:
F2n = F2n−1 + F2n−2 = (F2n−2 + F2n−3) + F2n−2 = 3F2n−2 − F2n−4 as desired.