Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


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.

share|cite|improve this question
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 I see the relation, thanks! – maq Nov 8 '10 at 18:26
@Ross please see edits – maq Nov 8 '10 at 18:41
up vote 1 down vote accepted

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

share|cite|improve this answer
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).

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.