0
$\begingroup$

enter image description here

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?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! This looks like a nice problem. Can you raise a question with enough detail to identify a good answer instead of just telling your story? At least one question mark is required. If this problem comes from an online source such as a coding camp or programming course, please provide a URL. If it comes from a book or a paper, a reference. That information, besides paying proper credits, motivate and help people answer the question faster and better. Please add those information in the question as people and search engine are not expected to look at comments. $\endgroup$ – Apass.Jack Oct 13 '18 at 17:30
  • 1
    $\begingroup$ "Since $0 \leq k - 1 < k$, this mean IH will apply to $FUN(x+3, y - 1)$". I cannot see how you can apply IH there, since $(x+3) + (y-1) = x+y+2 >k$. $\endgroup$ – Apass.Jack Oct 13 '18 at 17:34
  • $\begingroup$ Not sure what you mean @Apass.Jack, I edited the title to be a question. $\endgroup$ – Tree Garen Oct 13 '18 at 19:15
  • $\begingroup$ I have produced a suggested method of proof that accounts for the flaw pointed out by @Apass.Jack. I take $k=\min(x,\,y)$ rather than $k=x+y$. This does create two more complicated base cases, but I cover that also. $\endgroup$ – HackerBoss Oct 13 '18 at 21:53
  • $\begingroup$ @TreeGaren, can you provide us a URL or a reference to the original problem? I would like to check whether the original source contains the same error as I pointed out in my answer. $\endgroup$ – Apass.Jack Oct 15 '18 at 0:02
0
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.