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_{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. - Show that there do not exist any positive integers