2
$\begingroup$

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!

$\endgroup$
2
  • 4
    $\begingroup$ 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). $\endgroup$
    – Bumblebee
    Jul 21, 2020 at 5:42
  • $\begingroup$ @Bumblebee, it's not a tree because there are two paths to $(4,4)$. $\endgroup$
    – lhf
    Jul 21, 2020 at 12:46

1 Answer 1

2
$\begingroup$

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

$\endgroup$

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.