186 CHAPTER 8.
SOLUTIONS TO THE EXERCISES
Exercise 39. How many ternary strings of length 4 have zero ones?
Solution. We are looking at strings of length 4, and ternary means that the
symbols are 0,1 and 2. How if 1 is forbidden, in the first position of the string,
we have only 2 choices, and 2 choices for the 2nd, 3rd, and 4rth position.
Then a total of 24 choices.
Exercise 40. How many permutations are there of the word ”repetition”?
Solution. It is a word of length 10. Suppose we want to permute R, we have
10 choices. Now that R is fixed, we are left with 9 slots to fill. Let us try to
put the E. There are two E. Thus we have C(9, 2) ways to put them, since
we do not distinguish between the two of them. Then we have C(7, 1) = 7
for P, C(6, 2) for T, C(4, 2) for I, 2 choices for O, and 1 spot left for N. The
total is thus
9! 6! 4!
10 · C(9, 2) · 7 · C(6, 2) · C(4, 2) · 2 = 10 · ·7· · · 2.
7!2 4!2 4
We can simplify this expression to get
10 · 36 · 7 · 15 · 6 · 2.
Alternatively, we can use the formula
10!
=5·9·4·7·3·5·4·3·2
2!2!2!
and both of them give the same solution!
Exercises for Chapter 6
Exercise 41. Consider the linear recurrence an = 2an−1 − an−2 with initial
conditions a1 = 3, a0 = 0.
• Solve it using the backtracking method.
• Solve it using the characteristic equation.
187
Solution. • We have an = 2an−1 −an−2 , thus an−1 = 2an−2 −an−3 , an−2 =
2an−3 − an−4 , an−3 = 2an−4 − an−5 , etc therefore
an = 2an−1 − an−2
= 2(2an−2 − an−3 ) − an−2 = 3an−2 − 2an−3
= 3(2an−3 − an−4 ) − 2an−3 = 4an−3 − 3an−4
= 4(2an−4 − an−5 ) − 3an−4 = 5an−4 − 4an−5
= ...
We see that a general term is (i + 1)an−i − ian−(i+1) . Therefore the
last term is when n − i − 1 = 0 that is i = n − 1, for which we have
na1 − (n − 1)a0 , therefore with initial condition a0 = 0 and a1 = 3, we
get
an = 3n.
Optional. Now if one wants to be sure that this is indeed the right
answer, this can be checked using a proof by mathematical induction!
However here, the mathematical induction is slightly different from our
usual one! We have
P (n) = “an = 3n”,
so the basis step which is P (0) = “a0 = 0” holds. However we will also
need a second basis step, which is P (1) = “a1 = 3”, which still holds.
Now suppose P (k) = “ak = 3k 00 and P (k − 1) = “ak−1 = 3(k − 1)00 are
both true. Then
ak+1 = 2ak − ak−1
= 6k − 3(k − 1)
= 6k − 3k + 3 = 3k + 3 = 3(k + 1)
as needed, where we used both our induction hypotheses!
• Suppose now we want to solve the same recurrence using a character-
istic equation. We have xn = 2xn−1 − xn−2 that is
xn − 2xn−1 + xn−2 = 0 ⇐⇒ xn−2 (x2 − 2x + 1) = 0.
We have x2 − 2x + 1 = (x − 1)2 , therefore
an = u + vn.
188 CHAPTER 8. SOLUTIONS TO THE EXERCISES
Then
a0 = u = 0, a1 = u + v = 3
thus v = 3, yielding
an = 3n.
Exercise 42. What is the solution of the recurrence relation
an = an−1 + 2an−2
with a0 = 2 and a1 = 7?
Solution. The characteristic equation is x2 − x − 2 = 0. Its roots are x = −1
and x = 2 since (x+1)(x−2) = 0. Therefore an = u2n +v(−1)n is a solution.
We are left with identifying u, v using the initial conditions.
a0 = 2 = u + v, a1 = 2u − v = 7.
So u = 3, v = −1, therefore
an = 3 · 2n − (−1)n .
Exercise 43. Let an = c1 an−1 +c2 an−2 +. . .+ck an−k be a linear homogeneous
recurrence. Assume both sequences an , a0n satisfy this linear homogeneous
recurrence. Show that an + a0n and αan also satisfy it, for α some constant.
Solution. We have
an + a0n = (c1 an−1 + c2 an−2 + . . . + ck an−k ) + (c1 a0n−1 + c2 a0n−2 + . . . + ck a0n−k )
= c1 (an−1 + a0n−1 ) + c2 (an−2 + a0n−2 ) + . . . + ck (an−k + a0n−k ).
Thus an + a0n is a solution of the recurrence. Similarly
αan = α(c1 an−1 + c2 an−2 + . . . + ck an−k )
= c1 αan−1 + c2 αan−2 + . . . + ck αan−k .
Therefore αan is a solution of the recurrence.
