1

so the question is (to be solved with recurrence relations: How many numbers between 1 and 10,000,000 don't have the string 12 or 21?

So my solution: $a_n=10a_{n-1}-2a_{n-2}$. The $10a_{n-1}$ represents the number of strings of n length of digits from 0 to 9, and the $2a_{n-2}$ represent the strings of n-length with the 12 or 21 strings included.

Just wanted to know if my recursion is correct, if so, I'll be able to solve the rest.

Thanks in advance!

ohad
  • 633

2 Answers2

3

We look at a slightly different problem, from which your question can be answered.

Call a digit string good if it does not have $12$ or $21$ in it. Let $a_n$ be the number of good strings of length $n$. Let $b_n$ be the number of good strings of length $n$ that end with a $1$ or a $2$, Then $a_n-b_n$ is the number of good strings of length $n$ that don't end with $1$ or $2$.

We have $$a_{n+1}=10(a_n-b_n) +9b_n.$$ For a good string of length $n+1$ is obtained by appending any digit to a good string that doesn't end with $1$ or $2$, or by appending any digit except the forbidden one to a good string that ends in $1$ or $2$.

We also have $$b_{n+1}=2(a_n-b_n) + b_n.$$ For we obtain a good string of length $n+1$ that ends in $1$ or $2$ by appending $1$ or $2$ to a string that doesn't end with either, or by taking a string that ends with $1$ (respectively, $2$) and adding a $1$ (respectively, $2$).

The two recurrences simplify to $$a_{n+1}=10a_n-b_n\qquad\text{ and}\qquad b_{n+1}=2a_n-b_n.$$ For calculational purposes, these are good enough. We do not really need a recurrence for the $a_i$ alone. However, your question perhaps asks about the $a_i$, so we eliminate the $b$'s.

One standard way to do this is to increment $n$ in the first recurrence, and obtain $$a_{n+2}=10a_{n+1}-b_{n+1}.$$ But $b_{n+1}=2a_n-b_n$, so $$a_{n+2}=10a_{n+1}-2a_n+b_n.$$ But $b_n=10a_n-a_{n+1}$, and therefore $$a_{n+2}=9a_{n+1}+8a_n.$$

Remark: It would have been better to have $b_n$ as above, and $c_n$ the number of strings that do not end in $1$ or $2$, and to forget about $a_n$ entirely for a while.

André Nicolas
  • 507,029
  • Hey, thanks for the answer. I didn't understand the composition of the first equation. Why do you need to subtract the number of n-length strings who end with 1 or 2? And why do you then add $9b_n$? – ohad Jun 03 '13 at 04:59
  • The first two displayed equations, and the text around them, explain the reasoning. Nowhere are we subtracting, we are adding. When we simplify the expressions obtained, in the third displayed line, we end up with subtractions. These could be explained, but I preferred to make the explanation earlier, in terms of addition. One can also obtain the recurrence for $(a_n)$ directly, but I preferred not to do that, because the type of strategy I used earlier is of wider applicability, – André Nicolas Jun 03 '13 at 05:13
  • I just didn't understand the reasoning behind the first equation. Why do the sequences which end with 1 or 2 matter? Thanks. – ohad Jun 03 '13 at 18:09
  • Because in the natural way to set up the recurrence, the number of ways to "continue" depends on whether the last entry was $1$ or $2$, or something else. If it is $1$ or $2$, there are $9$ ways to continue. If is something else, there are $10$ ways to continue, nothing is forbidden. Setting up "states" like this is very important for many problems. – André Nicolas Jun 03 '13 at 18:16
  • You are welcome. In this case, we can obtain a second-order recurrence for $a_n$ directly. But systems of first-order linear recurrences can be very useful, since we can bring techniques of linear algebra to bear. We could now use "characteristic equation" techniques to find a closed form solution for $a_n$. However, for computational work, it is often easier and more reliable to work with the recurrences directly. – André Nicolas Jun 05 '13 at 14:48
1

I see that André answered this while I was out putting $52$ miles on my bicycle, but let me suggest a very slightly different route to the same recurrence that occurred to me during my ride. I’ll use the same good terminology and the same definition of $a_n$, and I’ll let $c_n$ be the number of good strings of length $n$ that do not end in $1$ or $2$.

Suppose that $\sigma$ is a good string of length $n\ge 1$. No matter what the last digit of $\sigma$ is, there are at least $9$ digits that I can append to $\sigma$ to make a good string of length $n+1$, and if the last digit of $\sigma$ is not $1$ or $2$, I can append any of the $10$ digits. This accounts for all possible good strings of length $n+1$, so $a_{n+1}=9a_n+b_n$. How many of these do not end in $1$ or $2$? Precisely the ones obtained by appending one of the $8$ digits in $\{0,3,4,5,6,7,8,9\}$ to a good string of length $n$, of which there are $8a_n$. Thus, $b_{n+1}=8a_n$, so $b_n=8a_{n-1}$, and

$$a_{n+1}=9a_n+b_n=9a_n+8a_{n-1}\;.$$

Thus, we have

$$\left\{\begin{align*} &a_0=1\\ &a_1=10\\ &a_n=9a_{n-1}+8a_{n-2}\quad\text{for}\quad n\ge 2\;. \end{align*}\right.$$

That’s as far as you had to go, but I was curious about a closed form for $a_n$. By standard techniques one can discover that

$$a_n=\frac1{226}\left(\left(113+11\sqrt{113}\right)\left(\frac{9+\sqrt{113}}2\right)^n+\left(113-11\sqrt{113}\right)\left(\frac{9-\sqrt{113}}2\right)^n\right)\;.$$

Now $$\left|\frac{9-\sqrt{113}}2\right|<1\quad\text{and}\quad\left|\frac{113-11\sqrt{113}}{226}\right|<0.02\;,$$

and $a_n$ is always an integer, so for $n\ge 1$ $a_n$ is the integer closest to

$$\frac{113+11\sqrt{113}}{226}\left(\frac{9+\sqrt{113}}2\right)^n\;.\tag{1}$$

$(1)$ is approximately $(1.017396477611)(9.815072906367)^n$.

For $n=7$ this evaluates to approximately $8,927,809.995842$, which rounds to $8,927,810$, the correct value, so the approximation is pretty good.

Brian M. Scott
  • 616,228