Help explaining Structural Induction I am trying to wrap my head around structural induction. Can someone break it down and explain it around this problem?

Let S, a subset of $\mathbb{N}*\mathbb{N}$, be defined recursively by:

Base case: $(0,0)$ $\in S$
Constructor case: If $(m,n) \in S$, then $(m+5,n+1) \in S$

Prove that if $(m,n) \in S$, then m+n is a multiple of 3.

How is it different than normal induction (using this example please) and what is the point of a Constructor case? Can someone wright the proof out so i can see what this structural induction proof looks like?
 A: The set $S$ is defined recursively: certain base elements of $S$ are specified, in this case just the ordered pair $\langle 0,0\rangle$, and a rule is given that allows ‘new’ elements of $S$ to be constructed from ‘old’ ones. Here each ‘old’ element $\langle m,n\rangle$ gives rise to just one ‘new’ one, $\langle m+5,n+1\rangle$. Thus, in this case
$$S=\{\langle 0,0\rangle,\langle 5,1\rangle,\langle 10,2\rangle,\langle 15,3\rangle,\ldots\}\;.$$
There is also a rule, often (as in this case) left unstated, to the effect that the only members of $S$ are the objects that can be obtained by repeatedly applying the constructor rule(s) to the base elements.
We can show that every member of $S$ has some property $P$ by first verifying that each of the base elements has $P$ and then showing that the construction process preserves the property $P$: that is, if we apply the construction process to objects that have $P$, the new objects also have $P$. If we can do this, we can conclude by structural induction that every member of $S$ has $P$.
In your problem an ordered pair $\langle m,n\rangle$ has the property $P$ if and only if $m+n$ is a multiple of $3$. This is clearly the case for the one base element $\langle 0,0\rangle$: $0+0=0=3\cdot 0$ is a multiple of $3$. That’s the base case of your structural induction. For the induction step assume that $\langle m,n\rangle\in S$ has $P$, i.e., that $m+n$ is a multiple of $3$. When we apply the construction process to $\langle m,n\rangle$, we get the pair $\langle m+5,n+1\rangle\in S$, and we want to show that it also has $P$, i.e., that $(m+5)+(n+1)$ is a multiple of $3$. By hypothesis $m+n=3k$ for some integer $k$, so
$$(m+5)+(n+1)=m+n+6=3k+6=3(k+2)\;;$$
and $k+2$ is an integer, so $(m+5)+(n+1)$ is indeed a multiple of $3$. We’ve now shown

*

*that the base element $\langle 0,0\rangle$ has the desired property, and

*that the construction process preserves this property: when applied to a pair $\langle m,n\rangle$ such that $m+n$ is a multiple of $3$, it produces another pair whose components sum to a multiple of $3$.

These are the base case and induction step of a proof by structural induction; between them they constitute a proof that $m+n$ is a multiple of $3$ for each $\langle m,n\rangle\in S$.
A: Mathematical induction is defined over natural number and it is based on two fundamental facts :


*

*there is an "initial" number : $0$

*every number $n$ has a unique successor : $n+1$.
Structural induction generalize this type of proof to "structures"  on which a well-founded partial order is defined, i.e.


*

*that have an "initial" or minimal element 


and


*

*they have a partial order.


It applies to structures recursively defined (such as lists or trees). 
