Fibonacci Sequence

let (f_k) be the Fibonacci sequence, show that: a) For every integer n>= 0, we have f_4(n+1) = 3f_4n+1 + 2f_4n b) Use a) in order to prove by induction that ∀n Є N, 3 | f_4n

Discrete mathematics: Boolean Product

Boolean Product. See attached file for full problem description.

Solve the system of congrunence

Solve the system: 2x ≡ 1 (mod 3) 3x ≡ 2 (mod 5) 5x ≡ 3 (mod 2)

Discrete Structures

1) If f is the mod-5 function, compute each of the following. a) f(17) b) f(48) c) f(169) 3) Convert (1011101)2 to base 16 (i.e., hex) 4) Find the sum of products expansion of this Boolean function F(x,y) that equals 1 if and only if x = 1. Note: one can write out the phrase “y complement” to represent the notation for the complement of y.

Show, how the given binary search algorithm executes in case of given key value.

Given algorithm looks for a value in a nondecreasing sequence and returns the index of the value if it is found or 0 if it is not found. Input: A sequence si, ...... ,sj (j >= i >= 1) sorted in nondecreasing order, a value key, i, and j Output: The output is an index k for which sk = key, or if key is not in the sequence, the output is the value 0. binary_search(s, i, j, key) { if (i > j) // not found return 0 k = (i + j)/2 if (key == sk) // found return k if (key < sk) // search left half j = k - 1 else // search right half i = k + 1 return binary_search(s, i, j, key) } Consider th... click for more