Intereting Posts

Find Distance Function from Acceleration Function
If $p$, $q$ are naturals, solve $p^3-q^5=(p+q)^2$.
How do i solve $e^{ax}-e^{bx}=c$ for $x$?
Legendre polynomials, Laguerre polynomials: Basic concept
Period of the sum/product of two functions
If series $\sum a_n$ is convergent with positive terms does $\sum \sin a_n$ also converge?
Binary expansion Unique
For $f$ continuous, show $\lim_{n\to\infty} n\int_0^1 f(x)x^n\,dx = f(1).$
Cover time chess board (king)
Is the matrix $A^*A$ and $AA^*$ hermitian?
Do all algebraic integers in some $\mathbb{Z}$ occur among the character tables of finite groups?
Determinant of a linear map given by conjugation
What is $\int_0^1 \ln (1-x) \ln \left(\ln \left(\frac{1}{x}\right)\right) \, dx$?
Proving $\sum_{k=0}^n\binom{2n}{2k} = 2^{2n-1}$
Measurability problem of sample distribution function of a contiuum of independent random variable

I know this problem is familiar to “the number of binary strings of length $n$ with no consecutive zeros” but still it is a way different problem.

But in that question the alphabet is set to $\{0,1\}$ and here:

**Q:**

Let $A=\{0,1,2\}$ be an alphabet, what is the the number of possible strings of length $n$ with no consecutive zeros in it?

- Coloring of an $1\times n$ board using 4 colors?
- Evaluate $ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2k}+\cdots$
- The number of ways to write a positive integer as the sum of distinct parts with a fixed length
- An Identity for Pell-numbers
- You have 6 red balls, 6 blue, and 6 white. You randomly select a sample of 3 balls without replacement.
- When is $\binom{n}{k}$ divisible by $n$?

- If $\{x_{2m}\}$ and $\{x_{2m-1}\}$ converge to the same limit, does $\{x_m\}$ converge?
- Number of unit squares that meet a given diagonal line segment in more than one point
- How many 0's are in the end of this expansion?
- Find the value of $\sum_{n=1}^{\infty} \frac{2}{n}-\frac{4}{2n+1}$
- Proof a graph is bipartite if and only if it contains no odd cycles
- Asymptotics of binomial coefficients and the entropy function
- lim inf $|a_n|=0 \implies \sum_{k=1}^\infty a_{n_k}$ converges
- Explicit solution of the recursion $x_n = x_{n-1}^2 - 2$ with $x_0>2$
- For a trigonometric polynomial $P$, can $\lim \limits_{n \to \infty} P(n^2) = 0$ without $P(n^2) = 0$?
- Combinatorics problem on $20$ people, $12$ months, and distinguishable groups

This is a general way that you can apply to this kind of problems (I’ll call the strings with no consecutive $0$’s, *good* strings.):

Let’s denote the number of good strings of length $n$ with $a_n$, and let’s define $b_n$ and $c_n$ to be the number of good strings starting with $0$ and starting with something other than $0$, respectively. So $a_n=b_n+c_n$.

Now, if a good string of length $n+1$ starts with $0$, then the string obtained by omiting the $0$, must start with something other than $0$, since no two consecutive $0$’s are allowed. Conversly, if you add a $0$ to the beginning of a good string of length $n$, starting with $1$ or $2$, then you get a good string of length $n+1$. So we have $b_{n+1}=c_n$.

Also, if a good string of length $n+1$ start with $1$ or $2$, by dropping the first element, we get a good string of length $n$. Conversly, adding $1$ or $2$ to the beginning of an arbitary good string of length $n$, results in a good string of length $n+1$. So we have $c_{n+1}=2a_n=2b_n+2c_n$.

Now combining the derived equations, we get (Note that we have those equations for *any* natural number $n$, so we can change the indices to any natural number we want.):

$$b_{n+2}=2b_{n+1}+2b_n$$

$$c_{n+2}=2c_{n+1}+2c_n$$

Summing up:

$$a_{n+2}=2a_{n+1}+2a_n$$

Now, you can use this recurrence relation for $a_n$.

It’s easy to see that similar to this way, you can solve the problems in which you want to find the number of strings in any finite language, that contain no instances of some finite patterns (like $102$, $11$ or so). Just define $b_n$, $c_n$, $\dots$ in a way that fits your problem, find the relations between them and combine them to find a recurrence relation for $a_n$.

A different approach, while not generic as @Mohsen Shahriari ‘s.

Lets break up by the number of zero’s contained in the sequence of length $n$. Suppose there are $k$ (max of $\frac{n}{2}$ when $n$ is even, $\frac{n + 1}{2}$ when $n$ is odd) zeroes. Using balls and sticks argument: We need to have some element between two $0$’s. There are $k-1$ gaps. After filling those gaps, we are left with $n – k – (k-1)$ of $1$’s and $2$’s to be filled in $k+1$ available places. This can be done in $\binom{n-2k+1 + k}{k}$ ways and $2^{n-k}$ ways to assign $1$’s and $2$’s.

Summing up,

$$\sum_{k = 0}^{v}\binom{n-k+1}{k} \cdot 2^{n-k}$$

where $v=\frac{n}{2}$ (when $n$ is even) and $v=\frac{n + 1}{2}$ (when $n$ is odd)

- Self-study resources for basic probability?
- Models of the empty theory
- Showing that $\log(\log(N+1)) \leq 1+\sum\limits_{p \leq N} \frac{1}{p}$
- If the set of values , for which a function has positive derivative , is dense then is the function increasing?
- How to calculate the limit of $\frac{a_n}{n^2}$ for the sequence $a_{n+1}=a_n+\frac{2 a_{n-1}}{n+1}$?
- A set with a finite integral of measure zero?
- rational functions on projective n space
- Optimal multiplying method
- $f$ is entire without any zeros then there is an entire function $g$ such that $f=e^g$
- Calculations in quotient rings
- Geometric Mean limit of $\ell_p$ norm of sums
- Simple proof that equilateral triangles have maximum area
- Proving path-connectedness of $\mathbb{R}^2\setminus\mathbb{E}$ where $\mathbb{E}$ is the set of points with both coordinates rational
- Can sum of a rational number and its reciprocal be an integer?
- Cyclic Group Generators of Order $n$