Discrete Mathematics Answers

1.    a) Recursively define a₀ = 1, a₁ = 3, a₂ = 5 and a_n = 3a_n-2 + 2a_n-3 for n ³ 3. Calculate a_n for n = 3,4,5,6

(4 Marks)

b) Find f(2), f(3), f(4) and f(5) for the following recursive functions.

                 f(0) = 1

f(1) = 2

f(k) = (f(k -1))² - f(k -2) + k²

(4 Marks)

Use Huffman coding to encode these symbols with given frequencies:

a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30.

What is the average number of bits required to encode a character?

(12 Marks)

Write an algorithm to finds the largest of the number a, b and c.

Suppose that a statement of the form ∀xP(x) is false. How can this be proved?

Translate in two ways each of these statements into logical expressions using predicates, quantifiers, and logical connectives. First, let the domain consist of the students in your class and second, let it consist of all people.

a) Someone in your class can speak Hindi.

b) Everyone in your class is friendly.

c) There is a person in your class who was not born in California.

d) A student in your class has been in a movie.

e) No student in your class has taken a course in logic programming.

Construct a combinatorial circuit using inverters, OR gates, and AND gates that produces the output

((¬p ∨¬r) ∧¬q) ∨ (¬p ∧ (q ∨ r)) from input bits p, q, and r.

Prove that for every positive integer ‘n’ : 1𝑋2𝑋3 + 2𝑋3𝑋4 + ⋯ + 𝑛(𝑛 + 1)(𝑛 + 2) =

𝑛(𝑛+1)(𝑛+2)(𝑛+3)