Suppose h₁: {0,1}^2m {0,1}^m is a collision resistant hash function.

(1) Define h₂: {0,1}^4m {0,1}^m as follows:

a. Write x{0,1}^4m as x=x₁||x₂, where x₁, x₂ {0,1}^2m.

b. Define h₂(x)=h₁(h₁(x₁)||h₁(x₂)).

Prove that h₂ is collision resistant.

(2) For an integer i 2, define a hash function h_i: {0,1}^{(2^i)m} {0,1}^m recursively from h_i-1, as follows:

a. Write x {0,1}^{(2^i)m} as x=x₁||x₂, where x₁, x₂ {0,1}^{(2^i)m}

b. Define h_i(x)=h₁(h_i-1(x1)||h_i-1(x₂)).

Prove that h_i is collision resistant.