1
$\begingroup$

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.

  • 2
    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.2010-11-08
  • 0
    Ahh ok yes you are right..now I see the relation, thanks!2010-11-08
  • 0
    @Ross please see edits2010-11-08

3 Answers 3

1

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)$

  • 0
    Wait x, x^2+1 is an element of M? I thought it was x, (x+1)^2 is an element of M2010-11-08
  • 0
    Right you are. Corrected.2010-11-08
  • 1
    Thanks, I was able to get the rest..2010-11-08
1

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).

1

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