Discrete Mathematics Answers

Determine whether each following statements about Fibonacci numbers is true or false

A. 2Fn >F n+1 for n≥3

B. 2F n+4 = f n+3 for n≥3

7. (a) Use the rules of Boolean algebra provided in (5) to simplify the following logic

gate circuit:

(b)Draw the simplified logic gate circuit in (a)

The recursive algorithm given below can be used to compute gcd(a, b) where a

and b are non-negative integer, not both zero.

procedure gcd(a, b)

if a > b then gcd(a, b) := gcd(b, a)

else if a = 0 then gcd(a, b) := b

else if a = 1 then gcd(a, b) := 1

else if a and b are even then gcd(a, b) := 2gcd(a/2, b/2)

else if a is odd and b is even then gcd(a, b) := gcd(a, b/2)

else gcd(a, b) := gcd(a, b − a)

Use this algorithm to compute

(a) gcd(124, 244) (b) gcd(4424, 2111).

Suppose that you meet three people Aiman, Borhan, and Camelia. Can you determine what Aiman, Borhan, and Camelia are if Aiman says "All of us are knaves" and Borhan says "Exactly one of us is a knave."?

State the Pigeonhole Principle. In a result sheet of a list of 60 students, each marked “Pass” or “Fail

“. There are 35 students pass. Show that there are at least two students pass in the list exactly nine

students apart. (for example students at numbered 2 and 11 or at numbered 50 and 59 satisfy the

condition).

How many cards must be selected from a standard deck of 52 cards to guarantee that at least three

cards of the same suit are chosen? How many must be selected to guarantee that at least 3 hearts

selected?

45 candidates appear in a competitive examination. Prove that there are at least two candidates

whose roll numbers differ by a multiple of 44.

A patient is given a prescription of 45 tablets with the instructions to take at least one tablet per day

for 30 days. Prove that there must be a period of consecutive days during which the patient takes a

total of exactly 14 tablets.