Problem $3$: $(15$ points$)$ One question computer scientists often ask is$,$Is the

algorithm correct?$$ Consider proving the correctness the following algorithm:

def fact$($n$)$:

if $($n $==1)$:

return $1$

else:

return n $*$ fact$($n$-1)$

Let P $($n$)$ be defined as: fact$($n$)=$ n$!$

$($a$)$ Correctness of fact$($n$)$: Prove that P $($n$)$ is true for all n in N$.$

$($b$)$ Write a recursive algorithm $($similar to fact$($n$))$ that calculates nn$.$

$($c$)$ Prove that n$!$ nn for all n in N