0
$\begingroup$

I've found this problem in "Discrete Mathematics and Application" by Kenneth Rosen. I also found an explanation of the way of solving this problem which goes like that,

Case 1: Start with a 1 – how many are these? If we remove the 1, then these strings are just the number of such strings of ܽan-1. Why? Because if you remove the 1, then all these strings must make the set ofܽ an - 1, i.e., strings of length ݊ − 1 that do not have two consecutive 0s.

Case 2: Start with a 0 – how many are these? These strings must also have a 1 at the second position. The number of such strings is ܽan-2. Why? Because if remove the last two digits “10”, these strings must make the set of ܽan-2, i.e., strings of length ݊n − 2 that do not have two consecutive 0s.

But i found it too complex, can anyone please make this a little bit easier ?

$\endgroup$
  • $\begingroup$ This has been asked repeatedly...see, e.g., this question $\endgroup$ – lulu Dec 2 '16 at 14:49
1
$\begingroup$

Let $a_{n}$ denote the number of strings of length $n$ that do not have consecutive $0$'s.
CASE $1$: Number of strings of length $n$ ending with $1$ is $a_{n-1}$.
CASE $2$: Number of strings of length $n$ ending with $10$ is $a_{n-2}$.
This yields the recurrence relation

$$a_{n} = a_{n-1} +a_{n-2}$$ for $$n\geq 3$$ where $a_{1}=1,a_{2}=3$.

$\endgroup$

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.