2
$\begingroup$

I need help executing a mathematical Induction for the following equation:

add(x,succ(y)) = succ(add(x,y))

I know that I have to either substitute n or m for "zero" for the Base Case, but I don't know what exactly I have to do after this.

To show: add(x,succ(y)) = succ(add(x,y))
Proof: Induction over x

Base Case: x = zero
To show: add(zero,succ(y)) = succ(add(x,y))

Proof 
add(zero,succ(y))
add(succ(y))

This is my attempt so far but I don't know how to follow up on this. I would really appreciate if someone could help me with this one.

$\endgroup$
  • 1
    $\begingroup$ What do you already know about the interaction between $\text{add}$ and $\text{succ}$ functions? $\endgroup$ – Joffan Jan 15 '17 at 19:17
  • $\begingroup$ Usually, what you state as claim is the definition of addition. It might be that your definition of addition uses recursion in x, then the question would make sense. Please add the relevant definitions to your question. $\endgroup$ – LutzL Jan 15 '17 at 21:05
1
$\begingroup$

Your base case framing is about right, but the steps you are taking are a little unclear.

Base case to show: $\text{add}(0,\text{succ}(y)) = \text{succ}(\text{add}(0,y))$

$\begin{align} \text{we know }\qquad\text{add}(0,k) &=k\\ \text{so }\quad\text{add}(0,\text{succ}(y)) &= \text{succ}(y) \\ \text{and }\quad\text{succ}(\text{add}(0,y)) &= \text{succ}(y) \end{align}$

Therefore the two expressions in the base case are the same, as required.

Inductive hypothesis: $\text{add}(x,\text{succ}(y)) = \text{succ}(\text{add}(x,y))$
Need to show: $\text{add}(\text{succ}(x),\text{succ}(y)) = \text{succ}(\text{add}(\text{succ}(x),y))$

$\begin{align} \text{we know }\qquad\text{add}(\text{succ}(a),b) &= \text{succ}(\text{add}(a,b))\\ \text{so }\quad\text{add}(\text{succ}(x),\text{succ}(y)) &= \text{succ}(\text{add}(x,\text{succ}(y))) \\ &= \text{succ}(\text{succ}(\text{add}(x,y))) \quad\text{by the hypothesis}\\ &= \text{succ}(\text{add}(\text{succ}(x),y)) \quad\text{as required}\\ \end{align}$

which completes the inductive proof.

$\endgroup$
  • $\begingroup$ thanks for your help and the great explanation. I really appreciate it :) $\endgroup$ – hey hoe Jan 15 '17 at 23:03
0
$\begingroup$

OK, so you know:

I. $add(0,x) = x$

II. $add(s(x),y) = s(add(x,y))$

And for the inductive proof you need to show:

Base: $add(0,s(y)) = s(add(0,y))$ ... which is true, since $add(0,s(y)) = s(y)$, and $s(add(0,y)) = s(y)$, both by I.

Step: Assume (Inductive Hypothesis) $add(x,s(y)) = s(add(x,y))$

We now want to show $add(s(x),s(y)) = s(add(s(x),y))$ (normally, you would go from $x$ to $x+1$, but in this case we go from $x$ to $s(x)$)

OK:

$add(s(x),s(y)) =$ (by II)

$s(add(x,s(y))) =$ (by Inductive Hypothesis)

$s(s(add(x,y))) =$ (by II)

$s(add(s(x),y))$

$\endgroup$
  • $\begingroup$ Yes, "add(zero, x) = x" and "add(succ(x1), x2) = succ(add(x1, x2))" is given $\endgroup$ – hey hoe Jan 15 '17 at 22:25
  • $\begingroup$ @heyhoe Ah! OK, in that case, Joffan's proof is how to do it! $\endgroup$ – Bram28 Jan 15 '17 at 22:34
  • $\begingroup$ OK, thank you for your help :) $\endgroup$ – hey hoe Jan 15 '17 at 22:40
  • $\begingroup$ @heyhoe No problem! Make sure to accept Joffan's answer if that indeed answers your question by clicking on the check mark next to Joffan's answer. $\endgroup$ – Bram28 Jan 15 '17 at 23:00

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.