Fibonacci Sequences

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 Products

2. For the zero-one matrix | 1 0 0 | B= | 0 1 1 | | 1 0 1 | A) Find B[2] = B ○ B and B[3] = B ○ B[2] B) Use a) and induction to fine B[n] = B ○ B ○…○B (n times) ********* Please note the ○ sign represent Boolean operator, there should be a dot the middle of this circle but I couldn’t find the symbol to enter it in my text so I used this instead. thanks*********** ... click for more

Solve the system of congruence

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