A friend posed a problem to me from his textbook today in where one was asked to create a recurrence relation for the number of strings of length $n$ in which there are no 3 consecutive digits. We assume we are using 26 characters and 10 digits for 36 symbols total.

I have been trying to figure it out, but I can't quite seem to get there.

I get the impression I can check my results in the following way:

$36^n - 36^{n-3} \cdot 10^3$

As that would be all possible strings of length $n$ with all possibilities of 3 consecutive numbers removed. I am not sure if i can check my results in this way, nor really how to start on the relation. This is a first year university course, so I imagine the solution doesn't need to be too deep.

How can one start to solve this problem?

  • $\begingroup$ No: $36^n-36^{n-3}10^3$ is not the correct answer. That counts the number of ways to get a string of $n$ letters that does not start with 3 digits. $\endgroup$ – Thomas Andrews Oct 29 '15 at 18:17
  • $\begingroup$ How does one proceed then? $\endgroup$ – user184881 Oct 29 '15 at 18:29

Let $A_n$ be the number of such strings. Then:

$$A_{n+1}=26A_n + 10\cdot 26 A_{n-1} + 10^2\cdot 26A_{n-2}$$

The closed form is messy, since the roots of $x^3-26x^2-260x-2600$ are irrational and only one, $r\approx 35.415$, is real. The closed form will be dominated by $cr^n$ for some constant $c$.

  • $\begingroup$ Could you expand on your answer? $\endgroup$ – user184881 Oct 29 '15 at 18:31
  • $\begingroup$ Can you think about it a bit longer? $\endgroup$ – Thomas Andrews Oct 29 '15 at 18:32
  • $\begingroup$ I just don't really understand it. I can sort of make sense of the formula, though not entirely. When it comes to your worded explanation, I haven't explored what roots or closed forms are in the context of such problems. $\endgroup$ – user184881 Oct 29 '15 at 18:35
  • $\begingroup$ Well, if you don't know the general method for solving linear recurrences, you won't understand the second paragraph, and explaining it is too long for an answer here. But you didn't actually ask for a closed form. $\endgroup$ – Thomas Andrews Oct 29 '15 at 18:38
  • $\begingroup$ You're right, I don't understand the second paragraph, unfortunately. I haven't learned the general method for solving linear recurrences. That being said, how do the terms used in your formula break up then? To me it seems like you are taking all strings that can be made by adding a letter in the first term, adding it with all the strings that could be made by adding a digit from the strings in n-1,which I am not sure I understand fully, and then my understanding completely falls apart with the last term. $\endgroup$ – user184881 Oct 29 '15 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy