Consider the set $S \subset \mathbb{N}^2$ of ordered pairs of integers defined by the following recursive definition:

• $(3, 2) \in S$ (basis)

• If $(x, y) \in S$, then $(3x − 2y, x) \in S$ (recursive step)

Also consider the set $S' \subset \mathbb{N}^2$ with the following non-recursive definition:

$$ S' = \{(2^{k+1} + 1, 2^k + 1) \mid k \in \mathbb{N}\}. $$

Prove using structural induction that $S \subseteq S'$.

  • $\begingroup$ That's false.. by your definition, $S$ may contain also (0,0) $\endgroup$
    – Exodd
    Sep 27, 2014 at 19:43
  • $\begingroup$ It's easy to prove the opposite: $S'\subseteq S$ $\endgroup$
    – Exodd
    Sep 27, 2014 at 19:45
  • $\begingroup$ how would I go about doing that? Don't I used complete induction to prove the opposite? It says I need to use structural induction. $\endgroup$ Sep 27, 2014 at 19:46
  • $\begingroup$ both ways are the same (if I get what you want): (3,2) is in the form of the element of $S'$, with $k=0$, but then the recursive step transform it in (5,3) that is also an element of $S'$ with $k=1$. Now, by induction, you shw that if $(x,y)=(2^{k+1}+1,2^k+1)$, then $(3x-2y,x)=(2^{k+2}+1,2^{k+1}+1)$ $\endgroup$
    – Exodd
    Sep 27, 2014 at 19:50
  • $\begingroup$ how would i go about showing it? like this: 3x - 2y = 2^(k+2)+1 and x = 2^(k+1)+1 so then 3(2^(k+1)+1)-2y=2^(k+2)+1 and I solve for y. I tried that came up with no conclustions @Exodd $\endgroup$ Sep 27, 2014 at 20:10

1 Answer 1


I'm assuming that $S$ is the smallest set containing $(3,2)$, and for each $(x,y) \in S$ also $(3x-2y,x) \in S$.

Hint: If $(x,y) \in S$ then for some $t \geq 0$, $(x,y)$ is obtained by $k$ applications of the recursive step. Use induction on $k$ to show that $(x,y) = (2^{k+1}+1,2^k+1)$. In the same way you can also prove the reverse inclusion, and conclude that $S = S'$.

  • $\begingroup$ Thank you!! I proved it this way. But the question says to prove using both structural and simple/complete induction. I feel I just proved it using simple/complete induction. How is structural suppposed to be different from this? For my proof k=1 and i proved 3x+2y = 2^(k+1)+1 $\endgroup$ Sep 27, 2014 at 20:42
  • $\begingroup$ The question is stupid. Structural induction in this case degenerates to simple induction. You should ask your instructor what they mean by the magic words "structural" vs. "simple". I suspect that is some pattern that they expect you to fill when writing up the proof which is slightly different in both cases. You can tell them from me that I think this is silly. Nobody should think this way. The idea of math is to identify common patterns, not to separate them in some arbitrary manner. $\endgroup$ Sep 27, 2014 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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