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.