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

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!

• The result is true for $(0,0)\in S.$ Assume the validity of the result for some arbitrary $(a,b)\in S$ and deduce the validity for next two branches of the tree (two new points defined via the recursion). Jul 21, 2020 at 5:42
• @Bumblebee, it's not a tree because there are two paths to $(4,4)$.
– lhf
Jul 21, 2020 at 12:46

1 Answer

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\}\,.$$