Discrete Mathematics for Computer Science

Exercises 567

Solution. Form the characteristic equation and then factor it:

c - 6c - 7 = 0

c =7, -1

Form the general solution of the recurrence relation a, = A7" + B (- 1)', and solve

the system of equations determined by the boundary values a3 =^344 and a4 =^2400 to get

the particular solution:

a3 = A7^3 + B(-1)'

a4 = A7^4 + B(--1)4

Now, substituting 344 and 2400 for a3 and a4 gives

344 = 343A - B

2400 = 2401A + B

Adding the two equations gives

2744 = 2744A

I=A

It follows that B = -1. Therefore, a,-- 7' + (-1)n+1 for n > 3 is the particular

solution. U

rnExercises

Solve Exercises 1 through 5 using the characteristic equation method.

1. an = 2an- -+3an - 2 for n >^2 where ao =^2 and a 1 = 2.

2. a, = 4a,_1 + 21a,-2 for n > 2 where ao = 3 and al = 7.

3. an + 8a- + 12a,-2 =^0 for n >^2 where ao = -2 and al = 6.

4. an - 8an-1 + 12an-2 = 0forn >^2 where a 0 =^3 and al = -1.

5. a, = 2an- I+ 15an-2 for n >^2 where ao =^3 andal -= -1.


6. How many binary sequences with no two consecutive O's are there of length k where
   k > 0? Exhibit all such sequences for length less than or equal to six. Determine the
   number of ways a coin can be flipped n times in which no two consecutive heads
   occur.


7. Let m, n e N. Using m colors, find and solve a recurrence relation that gives the num-
   ber of ways to color a disk with n sectors such that no pair of neighboring sectors
   receive the same color.


8. Find the number of arrangements of 1, 2, ... n such that no integer is more than one
   place removed from its position in the natural order 1 - 2 -... - n.


9. For students who have been introduced to the Backus-Naur forms, how many valid
   expressions can be formed using exactly k symbols from the set {0, 1, 2, 3, 4, 5, 6,
   7, 8, 9, +, -, /, *}, each with whatever repetition is desired. The normal form for an
   expression is
   expression > :: = < expression > < digit > I < expression > < sign > < digit >