To prove the correctness of the circuit in the 3rd question, will it suffice to find the recursive algorithm describing the circuit?
The recursion is fully described in the handout.
You need to prove (by induction) that this recursion indeed solves the problem it is intended to solve.