# Proving a Recursive Definition using Induction

I have the following recursive definition of a set $S \subseteq \mathbb N \times \mathbb N$ :

   Basis: (0, 0) in S.
Recursive step: If (m, n) in S then
(m, n + 1) in S,
(m + 1, n + 1) in S, and
(m + 2, n + 1) in S
Closure: The only points in S are those that can be generatede yb a
finite number of applications of the recursive step.


And I need to prove by induction (on the number of recursive steps) that

m <= 2*n forall (m, n) in S


The basis step i know how to do, simply show that (1,1) works with $m \le 2n$, but how would I show this in the inductive step? i have never done it like this so and am fairly new to induction, so please can you show me step by step how i would prove this. Thanks.

You need to show the following: Assume $m\le 2n$. Then if $(m',n')$ is any of the pairs $(m,n+1)$, $(m+1,n+1)$, $(m+2,n+1)$ then also $m'\le 2n'$. Indeed we have $$m'\le m+2\le 2n+2=2(n+1)=2n'.$$