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.

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

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