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