# Structural Induction Subsets

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'$.

• That's false.. by your definition, $S$ may contain also (0,0) Sep 27, 2014 at 19:43
• It's easy to prove the opposite: $S'\subseteq S$ Sep 27, 2014 at 19:45
• 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. Sep 27, 2014 at 19:46
• 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)$ Sep 27, 2014 at 19:50
• 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 Sep 27, 2014 at 20:10

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'$.