Proof the quadratic probing function

Question

I would really appreciate if someone could help solve this problem. The question is: Consider the following hash function: h(k, i) = (h’(k) + (1/2) (i + i^2 )) mod m, where m = 2^p for some positive integer p. Prove or disprove that for any k, the probe sequence is a permutation of <0, 1, 2, ...,m – 1>

Answer 1

Yes, it is.

Let's assume that h(k, i) = h(k, j).
Then h'(k) + 1/2 * i * (i + 1) = h'(k) + 1/2 * j * (j + 1) (mod m) <=>
1/2 * i * (i + 1) = 1/2 * j * (j + 1) (mod m) =>
i * (i + 1) = j * (j + 1) (mod 2m) <=> i * i - j * j + i - j = 0 (mod 2m) <=>
(i - j) * (i + j + 1) = 0 (mod 2m). The second term is odd and 2m = 2^(p + 1), thus
i = j (mod 2m) => i = j (mod m).