The Csatian language has the following two rules: (i) $B$ is a word, and (ii) if $x$ is a word then $BBBxxx$ is a word.

(a) Give an expression for the number of $B$s in a valid word.

(b) Suggest a third rule (iii) such that all multiples of 3 $B$s are valid words, and the only other valid word is a single $B.$

(c) Replace rule (iii) with the following: (iii) if $BBBBx$ is a word then $x$ is a word. Find all pairs $(p,q)$ such that, for all integers $n\ge0,$ the expression $pn+q$ gives the lengths of all valid words.

1. Find a closed form solution to the recurrence defined by $a_0=5, a_{n+1}=2a_n+1.$
2. The Climb language has two rules: (i) it contains the word $AAAAAAAA,$ and (ii) if $xx$ is a word, then $x$ is a word. Write down all the words in the language.
3. Give the possible values of $b$ in $3 \cdot 2^i \equiv b \mod 12$ for $i \in \{0,1,2,3, \ldots\}.$

(Part (a)) Find and solve a recurrence relation for the length of possible words.

(Part (b)) What is the characteristic of the valid words described by rule (ii)?

(Part (b)) … in terms of their divisibility?

(Part (b)) Rules (i) and (ii) only cover the case of a single $B$ and some multiples of 3 $B$s. How could rule (iii) cover all multiples of 3 $B$s, given that some multiples of 3 $B$s are valid words?

(Part (b)) Could you modify rule (iii) given in part (c) to do so? Note: Sometimes, reading the next part of the question helps.

(Part (c)) From the expression in part (a), find a new expression for the length of the valid words described by the new rule (iii).

(Part (c)) If you subtract $4k$ from the words described by rule (ii), do you get all the naturals?

(Part (c)) You should notice that by subtracting $4k$ from the words described by rule (ii), you are not guaranteed to get all naturals (why?). Which of those naturals are not possible? Try expressing them in a more general form.

(Part (c)) Prove that the new expression you get earlier could not be equal to those naturals. Hint: It is sufficient to show that the expression is not equal to the base case of the naturals (why?).

(a) We use the recurrence relation $l_i=3+3l_{i-1},$ which unwinds to give us:\begin{aligned} l_i&= 3+ 3(3+3l_{i-2}) \\ &=3+3^2+3^2 \cdot l_{i-2} \\ &=\sum_{k=1}^{i}3^k + 3^{i}\cdot l_0 \\ &=\frac{3(3^{i}-1)}{2}+3^{i} \\ &=\frac{5\cdot3^i-3}{2}. \end{aligned}

(b) Factorising $3$ from $l_i$ gives $\frac{5\cdot3^{i-1}-1}{2},$ whose numerator is divisible by $2,$ which means $l_i$ is a multiple of $3.$ Thus, if we want to obtain all multiples of $3$ as valid words, we can add a rule which subtracts $3$ $B$s from any valid word: “if $BBBx$ is a word then $x$ is a word”.

(c) You can write $l'_i=\frac{5\cdot3^i-3}{2}-4n,$ where $i,n$ are the number of applications of rule (ii) and (iii) respectively. But the question asks you to simplify this. From (a), $l_i$ is a multiple of $3,$ but it does not give all multiples of $3.$ Hence by subtracting $4n$ from it, you are not guaranteed to get all naturals, so it is not obvious which of the $4k,4k+1,4k+2,4k+3$ forms you can generate. The proof is in showing that $4k$ and $4k+3$ are not possible. One approach could be:

• Show that there do not exist any positive integers $i,n$ such that $\frac{5\cdot3^i-3}{2}-4n=4:$

Rearranging the given equation yields $5 \cdot 3^i - 8n = (2 \cdot 4) + 3 = 11,$ i.e. we require that $5 \cdot 3^i \equiv 11 \mod 8$. But for $i = 0,1,2,3,4$ we get $3^i \equiv 1, 3, 1, 3.$ This pattern repeats because:$$3^i \equiv 1 \mod 8 \implies 3^{i+1} \equiv 1 \cdot 3 \equiv3 \mod 8 \\ 3^i \equiv 3 \mod 8 \implies 3^{i+1} \equiv 9 \equiv 1\mod 8$$

Hence, $3^i \in \{1,3\}$ when taken $\text{mod }8$. Following that, $5 \cdot 3^i$ can only be $5 \cdot 1 \equiv 5$ or $5 \cdot 3 \equiv 15 \equiv 7$. Hence the equation can never be satisfied.

• Show that there do not exist any positive integers $i,n$ such that $\frac{5\cdot3^i-3}{2}-4n=3:$

Rearranging similarly, the problem becomes $5\cdot 3^i \equiv 9 \mod 8$. Using a similar argument as above, we get $5 \cdot 3^i$ is either $5$ or $7$ in $\text{mod }8,$ so the equation can never be satisfied.