I'm given that:
Let $S$ be the subset of the set of ordered pairs of integers defined recursively by:
Base case: $(0,0) \in S$
Recursive step: If $(a,b) \in S$, then $(a+1, b+3) \in S$ and $(a+3, b+1) \in S$
How do I use structural induction to show that for all $(a,b) \in S$ that $(a+b) = 4k$ for some $k \in \Bbb Z$?
Essentially, I believe I'm supposed to show that $(a+b)$ is divisible by $4$, but I'm at a bit of a loss in figuring out what steps I'm supposed to take here. Any help is greatly appreciated!
Let $p$ and $q$ denote, respectively, the operation $$(a,b)\mapsto (a+1,b+3)$$ and the operation $$(a,b)\mapsto (a+3,b+1)$$ for each $(a,b)\in S$. For each pair $(a,b)\in S$, let $\mu(a,b)$ denotes the minimum number of times the operations $p$ and $q$ are required to reach $(a,b)$, starting from $(0,0)$. We claim that $$a+b=4\,\mu(a,b)\,.$$
We shall induct on $\mu(a,b)$. If $\mu(a,b)=0$, then $(a,b)=(0,0)$. Clearly, $$a+b=0=4\cdot 0=4\,\mu(a,b)\,.$$ From now on, we suppose that $\mu(a,b)>0$. Hence, in a minimum sequence of operations to get $(a,b)$ from $(0,0)$, $(a,b)$ can be obtained from some $(a',b')\in S$ by either a use of $p$ or a use of $q$.
If $(a,b)$ is obtained from $(a',b')$ via the use of $p$, then $$(a,b)=(a'+1,b'+3)\,.$$ Therefoore, $$a+b=(a'+1)+(b'+3)=(a'+b')+4\,.$$ Using the induction hypothesis, $a'+b'=4\,\mu(a',b')$. Thus, $$a+b=4\,\mu(a',b')+4=4\,\big(\mu(a',b')+1\big)\,.$$ Obviously, $\mu(a,b)=\mu(a',b')+1$. Therefore, $a+b=4\,\mu(a,b)$, as required.
If $(a,b)$ is obtained from $(a',b')$ via the use of $a$, then $$(a,b)=(a'+3,b'+1)\,.$$ Therefoore, $$a+b=(a'+3)+(b'+1)=(a'+b')+4\,.$$ Using the induction hypothesis, $a'+b'=4\,\mu(a',b')$. Thus, $$a+b=4\,\mu(a',b')+4=4\,\big(\mu(a',b')+1\big)\,.$$ Obviously, $\mu(a,b)=\mu(a',b')+1$. Therefore, $a+b=4\,\mu(a,b)$, as required.
Remark. In fact, $\mu(a,b)$ is the number of times the operations $p$ and $q$ are required to reach $(a,b)$ from $(0,0)$, not just the minimum number. Furthermore, it can be shown that all $(a,b)\in S$ such that $\mu(a,b)=m$ for a given $m\in\mathbb{Z}_{\geq 0}$ are of the form $$(m,3m),(m+2,3m-2),(m+4,3m-4),\ldots,(3m,m)\,.$$ For $k=0,1,2,\ldots,m$, the element $(m+2k,3m-2k) \in S$ requires (in any order) $m-k$ times of the operation $p$ and $k$ times of the operation $q$. That is, $$S=\big\{(0,0),(1,3),(3,1),(2,6),(4,4),(6,2),(3,9),(5,7),(7,5),(9,3),\ldots\big\}\,.$$