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.

 Find a closed form solution to the recurrence defined by
$a_0=5, a_{n+1}=2a_n+1.$
 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.  Give the possible values of
$b$
in$3 \cdot 2^i \equiv b \mod 12$
for$i \in \{0,1,2,3, \ldots\}.$
 Find a closed form solution to the recurrence defined by

(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_{i1},$
which unwinds to give us:$$ \begin{aligned} l_i&= 3+ 3(3+3l_{i2}) \\ &=3+3^2+3^2 \cdot l_{i2} \\ &=\sum_{k=1}^{i}3^k + 3^{i}\cdot l_0 \\ &=\frac{3(3^{i}1)}{2}+3^{i} \\ &=\frac{5\cdot3^i3}{2}. \end{aligned}$$
(b) Factorising
$3$
from$l_i$
gives$\frac{5\cdot3^{i1}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^i3}{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^i3}{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^i3}{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.  Show that there do not exist any positive integers