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.