A valid database identifier of length $n$ can be constructed in three ways:
• Starting with $A$ and followed by any valid identifier of length $n − 1$.
• Starting with one of the two-character strings $1A, 1B, 1C, 1D, 1E,$ or $ 1F$ and followed by any valid identifier of length $n − 2$.
• Starting with $0$ and followed by any ternary $(\{0, 1, 2\})$ string of length $n − 1$.
Find a recurrence for the number $g(n)$ of database identifiers of length $n$ and then solve your recurrence to obtain an explicit formula for $g(n)$. (You may consider the empty string of length $0$ a valid database identifier, making $g(0) = 1$. This will simplify the arithmetic.)
I am having some trouble comprehending this one. First of all how is it possible to ever have $1A,...,1F$ if the only way you can get a $1$ is if there is a $0$ before it, and, in that case, the rest of the string has to be ternary. Also, the fact that it starts with these instead of ending is confusing me a little bit confusing to me. I went ahead and calculated the first couple possibilities to see if I could see somewhere but I am still confused.
$g(0)=1$
$g(1)=2$
$g(2)= 5 + 4 = 9$
This is a study question for my final exam tomorrow so any help would be very appreciated.
It’s not true that the only way to get a $1$ is to have a $0$ before it: the empty string is a ternary string, so $0$ is a valid identifier by the third clause, and then $1A0$ is a valid identifier by the second clause (and $A0$ by the first clause).
The third clause is the basis clause: it actually gives you explicitly a set of valid identifiers, namely, the ternary strings that start with $0$. The other two clauses tell you how to build more valid identifiers from any that you already have: if $u$ is a valid identifier, the strings $Au,1Au,1Bu,1Cu$, $1Du,1Du$, and $1Fu$ are valid identifiers.
Now suppose that $n\ge 2$. There are $g(n-2)$ valid identifiers of length $n-2$, and you can prefix any of the six strings $1A,\ldots,1F$ to each of them to get a valid identifier of length $n$ beginning with $1$; that’s $6g(n-2)$ identifiers. There are $g(n-1)$ valid identifiers of length $n-1$, and you can prefix $A$ to each of them to get a valid identifier of length $n$ beginning with $A$; that’s another $g(n-1)$ identifiers of length $n$, making a total of $g(n-1)+6g(n-2)$ valid identifiers of length $n$ beginning with $A$ or with $1$. How many are there that begin with $0$? They all come from the third clause. Add that in, and you’ll have a recursion for $g(n)$.