Could someone check my recursive program correctness proof that returns $F(x, y) \rightarrow x + y$?
As mentioned by Apass.Jack, you cannot apply IH to the $y&gt;0$ case, since $ (x+3)+(y-1)=x+y+2&gt;k$. I think you will want to do induction on $k=\min(x,\,y)$. Then you have no problem applying IH, since either $x$ or $y$ will always be smaller in the recursive call. The only difficulty here is that in your base case, you now need to cover when one of $x$ or $y$ is zero and the other is arbitrary. I will omit the case when both are zero, for brevity.

In the case that $y$ is zero, then the result will be $\text{FUN}(x-3,\,0)+3$. If $x$ is a multiple of 3 and positive, then this will eventually give $\text{FUN}(0,\,0)$ and then 3s will be added until you get $x$ again. This is what you wanted, since $x+y=x+0=x$. Note that the recursive calls retain the conditions that $x\geq0$ and a multiple of 3.

In the case that $x$ is zero, then the result will be $\text{FUN}(3,\,y-1)-2$, assuming your algorithm terminates, since if the algorithm took the $\text{FUN}(-3,\,y)+3$ branch, then there would be an infinite recursion. This implies that $y&gt;0$ initially. Then this branch will continue to be taken until $y=0$, in which case we will return $\text{FUN}(3y-3,\,0)+3$. This is the case when $x&gt;0$ and $y=0$, covered above. Then we get $3y-3+3-2y=y=0+y=x+y$. The $-2y$ comes from subtracting 2 recursively $y$ times.