Devise a recursive algorithm for computing $n^2$ where $n$ is a nonnegative integer, using the fact that $(n+1{)}^2=n^2+2n+1.$ Then

prove that this algorithm is correct.

procedure square$(n$ : nonnegative integer$)$

if $n=0$ then return $0$

else return square $(n-1)+2(n-1)+1$

Let $P(n)$ be the statement that this algorithm correctly computes $n^2.$ Because $0^2=0,$ the algorithm works correctly

$($using the if clause$)$ if the input is $0.$ Assume that the algorithm works correctly for input $k.$ Then for input $k+1,$ it

gives as output $($because of the else clause$)$ its output when the input is $k,$ plus $2(k+1-1)+1.$ By the inductive

hypothesis, its output at $k$ is $k^2,$ so its output at $k+1$ is $k^2+2(k+1-1)+1=k^2+2k+1=(k+1{)}^2,$ as desired.