A set M $\in$ $\mathbb{Z}^2$ is defined by
(Rule 1) $(0, 1)$ $\in$ M
(Rule 2) If $(x, y)$ $\in$ M, then $(x + 1, y + 2x + 3)$ $\in$ M
(a) (2 points) Starting with $(0, 1)$, write out the six pairs with the smallest first coordinates.
(b) (2 points) State the (simple) relationship that holds between the first and second coordinates of all pairs in M.
Ok for a I got: $(0,1)$,$(1,4)$,$(2,9)$,$(3,16)$,$(4,25)$,$(5,36)$,$(6,49)$
However for b, I cant see the relationship. Can anyone give me any hints?
EDIT:
Ok I found the relation: $y=(x+1)^2$. However, I must now prove this claim using structural induction. I can get up to the inductive hypothesis, but after that I'm not really sure what to do.
Base case: $(0,1), 1=(0+1)^2 = 1$
Inductive Hypothesis: For any element $x,y$ if $x\in M$ then $y=(x+1)^2$. We must show that $y+1=(x+1)^2 + 1$
I'm not really sure that my IH is correct either.