Proving a Recursive Definition using Induction

Question

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.

Answer 1

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'.$$