Could someone check my recursive program correctness proof that returns $F(x, y) \rightarrow x + y$?

Question

For $k \in \mathbb N$, we define $Q(k)$ as follows:

$Q(k): $ let $x, y \in \mathbb N$ and $x$ is a multiple of $3$ and $k = x + y$, then $FUN(x, y)$ terminates and returns $x + y$

I will prove $Q(k)$ using induction

Base Case: let $k = 0 \to iff (x = 0, y = 0)$

By line 1, 2, 5, $FUN(x, y)$ terminates and returns $0 + 0 = x + y$ as wanted

Inductive step: Let $k > 0$. Suppose $Q(j)$ holds whenever $0 \leq j < k$ [I.H]

What to prove: $Q(k)$ holds

Since $k > 0$, it follows that line 3-7 could run since line 1 is not satisfied.

Therefore two cases: $y > 0$ and $y \leq 0$

Case 1: If $y > 0$, then line 3, 4, and 7 will run.

Since $0 \leq k - 1 < k$, this mean IH will apply to $FUN(x+3, y - 1)$

By IH, $FUN(x+3, y - 1)$ terminates and returns $x + 3 + y - 1$

By line 3, 4 and 7. $FUN(x, y)$ terminates and returns $x + 3 + y - 1 - 2 = x + y$ by algebra, and as wanted

Case 2: If $y \leq 0$, then line 5, 6, and 7 will run since line 1, 3 are not satisfied

Since $0 \leq k - 1 < k$, this mean IH will apply to $FUN(x - 3, y )$

By IH, $FUN(x - 3, y )$ terminates and returns $x - 3 + y$

By line 5, 6 and 7. $FUN(x, y)$ terminates and returns $x - 3 + y + 3 = x + y$ by algebra, and as wanted

Therefore $Q(k)$ holds as wanted

This is my attempt above, not sure if I'm correct. I'm pretty confused on how to use IH in this or if my input size is even good. Is it correct?

Answer 1

Your proof had been very well written till it took a sudden turn at "Since $0 \leq k - 1 < k$, this mean IH will apply to $FUN(x+3, y-1)$". To be ale to apply the IH (induction hypothesis), it is required the sum of the arguments of $FUN$ must be smaller than $k$. However, since we are proving $Q(k)$, $x+y=k$. We have $(x+3)+(y-1)=k+2\gt k\ $, which means IH cannot apply to $FUN(x+3,y-1)\ $. So I am afraid your proof is incorrect.

In fact, your recursive program never terminates for any input! By carefully tracing the steps in your recursive program, you can verify that $FUN(0,0)$ will go into an infinite loop. Since the only possible way for the program to return any concrete result it must compute $FUN(0,0)$ at some moment, the program never terminates for any input. Apparently, line 2 of the problem is supposed to be (proper indent followed by) "return 0". Your proof is still incorrect for the corrected version of the program, though.

Indeed, it is non-trivial for a newcomer to come up with a rigorous proof since the easiest rigorous proof should involve induction on more than one counter, which is also called multidimensional mathematical induction.

Here is an outline of a correct proof. There are two steps.

1. let $\Bbb N$ be the set of 0 and positive integers. For $k\in\Bbb N$, we define $X(k)$ as the proposition that $FUN(3k, 0)$ terminates and returns $3k$. $X(k)$ can be proved by mathematical induction on $k$.

2. For $n\in\Bbb N$, define $Y(n)$ be the proposition that if $x$ is a multiple of 3, then $FUN(x, n)$ terminates and returns $x + n$. $Y(n)$ can be proved by mathematical induction on $n$. Note that the base case, $Y(0)$ is what is proved in step 1, all $X(k)$.

The hard part of the correctness proof of that algorithm and many similar ones is how to construct the propositions to facilitate mathematical induction on them. Once $X(k)$ and $Y(n)$ have been formulated as above, it is quite easy for anyone to fill the details of mathematical induction.

---

Here are two exercises that can be used to practice two-dimensional mathematical induction.

Exercise 1. Let $f:\Bbb N\times\Bbb N\to\Bbb Z$ such that $f(0,0)=0$. Furthermore, for any $m,n\in\Bbb N$, $f(m,n+1)=f(m,n)-2m+2n+1$ and $f(m+1, n)= f(m,n)+2m-2n+1$. Show that $f(m,n)=(m-n)^2$. (This can be proved by one-dimensional mathematical induction on $m+n$. The requirement here is, however, to prove it using a natural two-dimensional mathematical induction.)

Exercise 2. Prove the following algorithm, $PROD$ always terminates and returns the product of $x$ and $y$.

• Precondition: $x$ and $y$ are integers.
• Postcondition: Returns $xy$.
• $PROD(x,y)$:
  1. if both x and y are odd or one of them is 0:
  2.     return xy
  3. if x is even:
  4.     result = PROD(x/2, y) * 4
  5. else:
  6.     result = PROD(x, y/2) * 2
  7. return result

Answer 2

As mentioned by Apass.Jack, you cannot apply IH to the $y>0$ case, since $ (x+3)+(y-1)=x+y+2>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>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>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.