Problem $4.$ A recursive algorithm to compute the product of $x$ and $y$ is

FASTMULT $(x,y)$

Input: Two non$-$negative integers $x$ and $y$

Output: The product of $x$ and $y$

If $(y=0)$ return $0$

$z$:$=$ floor $(\frac{y}{2})$

$p$:$=$FAS$\frac{T}{M}ULT(x,z)$

If $y$ is even

Return $2p$

Else

Return $2p+x$

End$-$If

Prove by induction that this algorithm works.