Answer the following questions about the Square function below:

Input: $n$ : nonnegative integer

Output: $n^2$

Algorithm: Square $(n)$

if $n=0$ then

return $0$

else if $n$ is even then

$t=$Square$(\frac{n}{2})$

return $4t$

else

$t=$Square$(\frac{n-1}{2})$

return $4t+2n-1$

end

Prove the base case of the proof that Square$(n)$ returns $n^2$ for all $n0.$

What is the strong induction hypothesis of the proof that Square $(n)$ re$-$

turns $n^2$ for all $n0?$

What is the induction goal of the proof that Square $(n)$ returns $n^2$ for all

$n0?$

Prove the induction step of this proof.

Hint: you will need to argue that the argument to the recursive call is a

nonnegative integer. An integer $x$ is even if and only if there exists some

integer $y$ such that $x=2y.$ Every integer that is not even is odd, and

an integer $x$ is odd if and only if there exists some integer $y$ such that

$x=2y+1.$