# Find a pattern in a recursive definition

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.

-
It appears you are using the new x in the calculation of y. I believe you should use the old x. So the second pair should be (1,4). All will become clearer. – Ross Millikan Nov 8 '10 at 18:21
Ahh ok yes you are right..now I see the relation, thanks! – maq Nov 8 '10 at 18:26
@Ross please see edits – maq Nov 8 '10 at 18:41

Your inductive step is to show that if $(x,(x+1)^2) \in M$, then $(x+1,(x+2)^2) \in M$. So apply Rule 2 to $(x,(x+1)^2)$

-
Wait x, x^2+1 is an element of M? I thought it was x, (x+1)^2 is an element of M – maq Nov 8 '10 at 18:56
Right you are. Corrected. – Ross Millikan Nov 8 '10 at 19:04
Thanks, I was able to get the rest.. – maq Nov 8 '10 at 19:06

Your inductive hypothesis is wrong. You should be showing that if $(x,(x+1)^2)\in M$, then $(x+1, ((x+1)+1)^2) \in M$. From there you should be able to see how to get the result (just use Rule 2).

-

HINT $\rm\ \ f\ (x,\:y)\ = \ (x+1,\ y+2x+3)\ \Rightarrow\ f\ (x,\ (x+1)^2)\ =\ (x+1,\ (x+2)^2)$

-