Intereting Posts

Logical errors in math deductions
Question on the symmetric product $\mathrm{Sym}^g\Sigma$
How to express the statement “not all rainy days are cold” using predicate logic?
Why is the sum of residues of $\frac{1}{1+z^n}$ in the upper half plane $1/$?
About polar coordinates in high dimensions
Is the degree of an infinite algebraic extensions always countable?
Example of a relation that is symmetric and transitive, but not reflexive
Simple Double Summation
Is this AM/GM refinement correct or not?
Is the series $\sum \sin^n(n)$ divergent?
How to find the center of an ellipse?
How come that two inductive subsets can be different
for $1<p<2$, prove the p-series is convergent without concerned with integral and differential knowledge and geometry series
Given a joint characteristic function, find $P(X<Y)$
Why are continuous functions the “right” morphisms between topological spaces?

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?

- Proof sought for a sum involving binomials that simplifies to 1/2
- combinatorics olympiad problem - sort out a schedule
- Number of positive integral solution of product $x_{1} \cdot x_{2} \cdot x_{3}\cdot x_{4}\cdot x_{5}=1050$ is
- Counting strings containing specified appearances of words
- A game of guessing a chosen number
- Rearranging people so that no one is in the same spot

- How can I prove this closed form for $\sum_{n=1}^\infty\frac{(4n)!}{\Gamma\left(\frac23+n\right)\,\Gamma\left(\frac43+n\right)\,n!^2\,(-256)^n}$
- Not lifting your pen on the $n\times n$ grid
- Why is this series of square root of twos equal $\pi$?
- Find $\lim_{n \to \infty} \sqrt{n!}$.
- Prove $\sum_{k=1}^{\infty} \frac{\sin(kx)}{k} $ converges
- Closed form of $\int_0^1(\ln(1-x)\ln(1+x)\ln(x))^2\,dx$
- Reference request: Introduction to mathematical theory of Regularization
- How to prove $\sum_{n=0}^{\infty} \frac{n^2}{2^n} = 6$?
- Combinatorics: Color a wall such that not two neighbored slots have the same color
- Convergence of $x_{n+1} = \frac12\left(x_n + \frac2{x_n}\right).$

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)

- Functions such that $f(f(n))=n+2015$
- Let $p$ be prime and $(\frac{-3}p)=1$. Prove that $p$ is of the form $p=a^2+3b^2$
- Automorphism of $S_4$
- symbolic computation program/software
- How many planar arrangements of $n$ circles?
- Are all values of the totient function for composite numbers between two consecutive primes smaller than the totient values of those primes?
- Verifying a proposition on image and preimage: $f(A\cap B)\subseteq f(A)\cap f(B)$ and $f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)$
- Example of a ring without unity that has a subring with unity?
- Examples where $H\ne \mathrm{Aut}(E/E^H)$
- Weak convergence and strong convergence
- Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice?
- Why is integration so much harder than differentiation?
- Why is it important to study the eigenvalues of the Laplacian?
- the solution for an integral including exponential integral function
- Prove that there exists a Borel measurable function $h: \mathbb R \to \mathbb R$ such that $g= h\circ f$.