0
$\begingroup$

For n ≥ 0 let a(n) be the number of quinary strings (only contain digits among 0 . . . 4) of length n and do not contain the string 00. Find a recurrence relation and give initial conditions for the sequence a0 , a1, ...

Completely confused with this question, how do I go about find a recurrence relation for a quinary string?

Improve this question
$\endgroup$
0
$\begingroup$

Let a string be called valid when it has your property. Let $a_n$ denote what you mentioned. Let $c_n$ denote the number of $n$ digit quinary strings without $00$ with the additional condition that the string does not have a $0$ at the end. Let $b_n$ denote the number of $n$ digit quinary strings without $00$ with the additional condition that the string has a $0$ at the end. It is easy to see that $a_n=b_n+c_n$. Also, one has these relations: $$b_{n+1}=c_n$$ $$c_{n+1}=4a_n=4(b_n+c_n)$$ The first one comes from the fact than any valid string with no $0$ at its end can be extended to a valid string with a $0$ at the end by appending a $0$. For the second one, if we have any valid string then we can append one of $1,2,3,4$ at its end to get a valid string without a $0$ at its end. Using this, we get $c_{n+1}=4(c_n+c_{n-1})$ and $b_{n+1}=4(b_n+b_{n-1})$ and on adding we get $a_{n+1}=4(a_n+a_{n-1})$.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the quick answer, Manan! Unfortunately, I am still a bit confused with your explanation... $\endgroup$ – Audrey Kan May 11 '18 at 5:38
  • $\begingroup$ A) In the first part of your answer you say a(n) = b(n) + c(n). So an example of that would be 140230 = 1402 + 30. B) Then, I am also confused with the second relation c(n+1) = 4a(n)... where does the 4 come from? $\endgroup$ – Audrey Kan May 11 '18 at 5:44
  • $\begingroup$ We need to find $a_n$. First, we break $a_n$ into two parts $b_n$ and $c_n$. $b_n$ counts the number of $n$ digit valid strings with a $0$ at the end, and similarly no zero at the end for $c_n$. We are not breaking up the string itself. We are just counting valid strings with complementary properties and then adding up to get the total number of valid strings. $\endgroup$ – Manan May 11 '18 at 5:46
  • $\begingroup$ A string contributes to $c_{n+1}$, that is, is of $n+1$ length and is valid without a $0$ at the end if and only if its last digit is not $0$ and the string formed by its first $n$ digits is valid. Now, the last digit has $4$ non zero choices, namely $1,2,3,4$ and the number of valid strings with $n$ digits is just $a_n$. $\endgroup$ – Manan May 11 '18 at 5:49

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.