Recall that Fk denotes the kth Fibonacci number: F0 = 0, F1 = 1, and Fk = Fkô€€€1 + Fkô€€€2 for allk 2. Suppose we are building a hash table of size m = Fk using the hash functionh(x) = (Fkô€€€1 x) mod FkProve that if the consecutive integers 0, 1, 2, . . . , Fk ô€€€1 are inserted in order into an initially emptytable, each integer will be hashed into the largest contiguous empty interval in the table. Inparticular, show that there are no collisions.