0

There's a problem that goes as follows:

Let $a_n$ be the number of binary strings of length $n$ in which there are no consecutive 0s. Show that $a_1 = 1, a_2 = 3$ and that $a_n = a_{n-1} + a_{n-2}$

I am not sure how exactly am I supposed to "show" the final bit. Proofs by induction involve the closed formula for $a_n$.

Is there a formal, general proof to this or do I have to show using words and possibly figures?

alexandrosangeli
  • 115
  • https://oeis.org/A000204 – Raffaele Feb 13 '21 at 16:31
  • @JoséCarlosSantos Not quite. If we can show that a string of length n can be constructed by appending 1 to a string of length n -1 or appending 10 to a string of length n - 2 then why stop there? Why not append 101 to a string of length n - 3 ? Or why not append 11 to a string of length n - 2 instead of 10? – alexandrosangeli Feb 13 '21 at 16:34
  • Why not append $101$ to a string of length $n-3$? Because that's included in appending $10$ to a string of length $n-2$. – José Carlos Santos Feb 13 '21 at 16:36
  • So, how is 10 not included in appending 1 to a string of length n - 1 though? – alexandrosangeli Feb 13 '21 at 16:40
  • What is your exact question ? I don't know what you call "this". –  Feb 13 '21 at 17:41

1 Answers1

2

In several cases in recurrence relationships, the recurrence is due to the nature of the objects which allow them to be put into disjoint classes, each of which has as number of elements the number of elements given by a previous number of the recurrence. Not all recurrences have such a straight forward interpretation, nor all objects to count can be put into a nice looking recurence, tho.

In the case at hand, if $S$ is the set of all these binary sequences there is a natural splitting into two subsets: $S_0$, $S_1$ are those sequences that start with $0$ and $1$, respectively. Clearly $S = S_0 \cup S_1$, and this union is a disjoint union, so that $a_n = |S| = |S_0| + |S_1|$.

Now notice how if you already put a $1$ at the start, then you can put whatever valid combination (i.e. not two consecutive 0's allowed) after it and generate one of the sequences from $S$. So $S_1$ has as number of elements just $a_{n - 1}$.

On the other hand, this doesn't work immediately if you start with a $0$, since you cannot put immediately another $0$, since you would have $00...$ which is not valid, so by force, you put a $1$ to begin with $01...$ and then you have $n - 2$ slots to fill now in any way, as long as there are not two $0's$. Hence, $S_0$ has as number of elements $a_{n - 2}$.

You conclude from this $a_n = a_{n - 1} + a_{n - 2}$.

MEEL
  • 761