Question $1$

Induction is a powerful tool to prove the correctness of recursive algorithms. Consider the algorithm below for incrementing a positive integer number recursively $($i$.$e$.,$ INCREMENT $(x)x+1)$:

function INCREMENT $)(0$

if $x=0$ then

return $1$

else

if $x$ is even then

return $x+1$

else

return $2-$ INCREMENT $({|}_{{?}_{?}}\frac{x}{2_{{?}_{?}}}|)$

end if

end if

end function

For the following items, focus on the proof by induction. No need to state and prove an invariant.

$($a$)$ State the mathematical recurrence relation followed by the algorithm.

$($b$)$ State the inductive hypothesis $P(n).$

$($c$)$ Show the base case $P(0)$ is true.

$($d$)$ Prove $P(x).$