Discrete Mathematics Answers

∑ (2 𝑗+1 − 2 𝑗 ) 8 𝑗=0 

L

ist

five situation from da

ily life in which

graphs ar

ise natu

rally

Determine values of the constants A and B such that an = An + B is a solution of

recurrence relation an = 2an−1 + n + 5. Hence, find the solution of this recurrence

relation with a0 = 4.

Consider the nonhomogeneous linear recurrence relation an = 3an−1 + 2^n. Show

that a^n = – 2^(n+1) is a solution of this recurrence relation.

Suppose that G is a connected multigraph with 2k vertices of odd degree. Show that there exist k subgraphs that have G as their union, where each of these subgraphs has a Euler path and where no two of these subgraphs have an edge in common.

Suppose a recurrence relation

an=an−1+20an−2

where a1=9 and a2=189

can be represented in explicit formula, either as:

Formula 1:

an=pxn+qnxn

                      or  

Formula 2:

an=pxn+qyn

where 

x

and

y

are roots of the characteristic equation.

**If the explicit formula is in the form of Formula 2, consider p > q.

Determine p and q

Answer:

Suppose you want to encode messages containing only the following characters with their given respective frequencies: B: 55 D: 15 E: 80 G: 5 U: 45

(a) What is the minimum length bit string required to encode each character with a distinct, fixed-length code?

(b) Construct the Huffman Tree for the characters with the given frequencies. (Use the convention that when merging two vertices, the vertex with the largest count goes on the left.)

(c) Use your Huffman Tree to decode the message M = 00101010000011

(d) How many bits are required to encode the characters with the given frequencies using the Huffman Encoding and the fixed-length encoding you found in part (a)? How much storage savings does this represent?

Write each of these statements in the form “if p, then q”

in English. [Hint: Refer to the list of common ways to express

conditional statements provided in this section.]

a) It is necessary to wash the boss’s car to get promoted.

b) Winds from the south imply a spring thaw.

c) A sufficient condition for the warranty to be good is

that you bought the computer less than a year ago.

d) Willy gets caught whenever he cheats.

e) You can access the website only if you pay a subscription

fee.

f ) Getting elected follows from knowing the right people.

g) Carol gets seasick whenever she is on a boat.

What is the truth value of ∀xP(x), where P(x) is the statement “x² < 10” and the domain consists

of the positive integers not exceeding 4?