Proof of property by mathematical Induction

Question

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.

Answer 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.

Answer 2

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