# Find a recursion formula for combinatorial problem. Let C_n be the number of sequences with a length of n, which their elements belong to {0,1,2}, and they don't contain the following sequences: 11,21. Find a recursion formula with starting conditions for C_n.

Find a recursion formula for combinatorial problem
Let ${C}_{n}$ be the number of sequences with a length of n, which their elements belong to {0,1,2}, and they don't contain the following sequences: 11,21. Find a recursion formula with starting conditions for ${C}_{n}$.
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Aliya Moore
Step 1
If the last digit is a 0 or a 2, any sequence of length $n-1$ works before that, and if the last digit is a 1, the rest of the sequence has to end in a 0, which in turn means that the first $n-2$ digits have to form an arbitrary valid sequence. From there we immediately arrive at the recursive formula ${C}_{n}=2{C}_{n-1}+{C}_{n-2}$.
Now as promised the more complicated approach considering the first digit: Let ${x}_{n}^{\left(k\right)}$ denote the number of sequences of length n that start with the digit k, obviously we have ${C}_{n}={x}_{n}^{\left(0\right)}+{x}_{n}^{\left(1\right)}+{x}_{n}^{\left(2\right)}$. Let's find recursive formulas for the ${x}_{n}^{\left(k\right)}$. For $k=0$, we have
${x}_{n}^{\left(0\right)}={x}_{n-1}^{\left(0\right)}+{x}_{n-1}^{\left(1\right)}+{x}_{n-1}^{\left(2\right)}={C}_{n-1}$
since a 0 can be added to every sequence of length $n-1$. For $k=1$ and $k=2$, the rest of the sequence may not start with a 1, so we have
${x}_{n}^{\left(1\right)}={x}_{n}^{\left(2\right)}={x}_{n-1}^{\left(0\right)}+{x}_{n-1}^{\left(2\right)}.$
Step 2
Now we put this together and calculate a formula for ${C}_{n}$:
$\begin{array}{rl}{C}_{n}& ={x}_{n}^{\left(0\right)}+{x}_{n}^{\left(1\right)}+{x}_{n}^{\left(2\right)}={C}_{n-1}+2\left({x}_{n-1}^{\left(0\right)}+{x}_{n-1}^{\left(2\right)}\right)\\ & ={C}_{n-1}+{x}_{n-2}^{\left(0\right)}+{x}_{n-2}^{\left(1\right)}+{x}_{n-2}^{\left(2\right)}+{x}_{n-1}^{\left(0\right)}+2{x}_{n-1}^{\left(2\right)}\\ & ={C}_{n-1}+{x}_{n-1}^{\left(1\right)}+{x}_{n-2}^{\left(1\right)}+{x}_{n-1}^{\left(0\right)}+{x}_{n-1}^{\left(2\right)}+{x}_{n-1}^{\left(2\right)}\\ & =2{C}_{n-1}+{x}_{n-2}^{\left(1\right)}+{x}_{n-2}^{\left(0\right)}+{x}_{n-2}^{\left(2\right)}\\ & =2{C}_{n-1}+{C}_{n-2}.\end{array}$