2

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.

hey hoe
  • 35
  • 4
  • 1
    What do you already know about the interaction between $\text{add}$ and $\text{succ}$ functions? – Joffan Jan 15 '17 at 19:17
  • 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. – Lutz Lehmann Jan 15 '17 at 21:05

2 Answers2

1

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.

Joffan
  • 39,627
0

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))$

Bram28
  • 100,612
  • 6
  • 70
  • 118