Recurrence relation - How To Give a Combinatorial Proof

Question

Problem:

Consider the set $S$ of all “ternary strings” (strings in the ‘alphabet’ {$0$, $1$, $2$}), such that a $0$ never is directly followed by a $1$ or a $2$. (Thus, e. g. the strings $12100$ and $21122211$ belong to $S$, but $12012$ does not.) For $n = 0, 1, 2,...,$ let $s_n$ be the number of strings in $S$ of length $n$.

a) Prove, that $s_n$ = $1$ + $2s_{n−1}$ for each $n\geq 1$, by means of a combintorial argument.

b) Exhibit the generating formal power series (a. k. a. ‘the generating function’) for $S$ as the quotient of two polynomials.

c) Provide a closed expression of $s_n$, as an explicit function of $n$.

---

Solution:

b) and c) were easily solved. For b) I just defined the function $f(y)=\frac{1}{1-y}=1+y+y^2+y^3...$ by substituting $2x$ I get $f(2x)=\frac{1}{1-2x}=1+2x+(2x)^2+(2x)^3+...$, but since the sequence looks like 1, 3, 7, 15... (that is $2^{n+1}-1$) i have to subtract $\frac{1}{1-x}$, and so my generating function g is $g(x) = \frac{1}{1-2x} - \frac{1}{1-x}=\frac{x}{(x-1)(2x-1)}$. I have actually already answered c), but all i did was looking for a pattern and then concluded the formula $2^{n+1}-1$. My problem lies in part a).

I really want to learn how to make combinatorial proofs but I think it's pretty hard and I usually don't understand how to start. When I study something, combinatorics in this case, I really want to learn how to think combinatorial for example more than just trying to memorize everything. This is also something which will be important to know for my upcoming exam and I would be really happy if someone could help me out.

---

My attempt:

a) For $s_1$ we have three different such strings, that is, $S=\{0,1,2\}$. Consider now the case for $n=2$, then we have,

$$\text{(a) } 0\_$$ $$\text{(b) } 1\_$$ $$\text{(c) } 2\_$$

At the end of every string we can attach a string from the alphabet $0, 1, 2$. We can therefore count the previous ($s_{n-1}$) in both (b) and (c) (hence $s_{n-1}+s_{n-1}=2*s_{n-1}$. Since (a) starts with an $0$ we have to attach an $0$ at the end of that string too and that makes 1 and so $s_n=1+2s_{n-1}$. I would like to generalize this reasoning but when I start to think about $n=3$ for example I get pretty confused and don't really believe in my own argument anymore. So could someone please help me? Thanks :)

Answer 1

Strings of length $n$ can be formed from strings of length $n-1$ by prepending 1 or 2 (this works for all $s_{n-1}$ of them) or 0 (this works for only one of them, the string consisting of $n-1$ zeroes).

Answer 2

Say that a string is good if it does not contain $01$ or $02$. One of the most straightforward approaches actually leads to a second-order recurrence, as follows. Let $a_n$ be the number of good strings of length $n$ ending in $0$, $b_n$ the number ending in $1$, and $c_n$ the number ending in $2$. Of course $s_n=a_n+b_n+c_n$.

Now suppose that $\sigma$ is a good string of length $n$, and let $\tau$ be the string of length $n-1$ obtained by removing the last character of $\sigma$.

• If $\sigma$ ends in $0$, $\tau$ can be any good string of length $n-1$, so $a_n=s_{n-1}$.

• If $\sigma$ ends in $1$, $\tau$ can be any good string of length $n-1$ that ends in $1$ or $2$, so $b_n=b_{n-1}+c_{n-1}$.

• And if $\sigma$ ends in $2$, $\tau$ can again be any good string of length $n-1$ that ends in $1$ or $2$, so $b_n=b_{n-1}+c_{n-1}$.

Thus,

$$\begin{align*} s_n&=a_n+b_n+c_n\\ &=s_{n-1}+2(b_{n-1}+c_{n-1})\\ &=s_{n-1}+2(s_{n-1}-a_{n-1})\\ &=3s_{n-1}-2a_{n-1}\\ &=3s_{n-1}-2s_{n-2}\;. \end{align*}$$

However, a minor rearrangement yields the equation

$$s_n-2s_{n-1}=s_{n-1}-2s_{n-2}\;,$$

which says that the difference $s_n-2s_{n-1}$ is a constant independent of $n$, and we must have

$$s_n-2s_{n-1}=s_1-2s_0=3-2\cdot1=1$$

and hence $$s_n=2s_{n-1}+1$$

for all $n\ge 1$.

While it’s often good to look at what happens when a character is removed from (or added to) the righthand end of the string, in this problem it’s actually better to look at the other end of the string: you get the desired first-order recurrence directly. I was going to add this, but I see that Justpassingby has done it very nicely.