Recursive Algorithm $($postponed fom Hmw$3)$

Recall that Z

$+=\{1,2,3,...\}.$ Consider the following recursive algorithm mystery:

Algorithm mystery$($n$)$: $($assume n in Z

$+)$

If n $=1$ or n $=2$ then return n

else return mystery$($n$1)+2$ mystery$($n$2)$

Here are examples of how mystery would exectue on a few first inputs n in Z

$+$:

mystery$(1)$ returns $1$ by the base case,

mystery$(2)$ returns $2$ by the base case,

mystery$(3)$ returns mystery$(2)+2$ mystery$(1)=2+21=4,$

mystery$(4)$ returns mystery$(3)+2$ mystery$(2)=[...]$

Do two things: $(1)$ state a closed$-$form formula for function f$($n$)$ s$.$t$.$ f$($n$)$ is the output of

mystery$($n$),$ for every n in Z

$+,$ and $(2)$ use induction to prove that mystery$($n$)=$ f$($n$)$ for all n$.$