Question

How many ternary strings of length six contain two consecutive 0's ?

Short answer

There are 281 ternary strings of length six that contain two consecutive 0's.

Step-by-step solution

Given data

The person climbing the stairs can take one, two, or three stairs at a time.

Concept used of recurrence relation

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing${\mathit{F}}_{\mathbf{n}}$as some combination of${\mathit{F}}_{\mathbf{i}}$with$\mathit{i}\mathbf{}\mathbf{<}\mathbf{}\mathit{n}\mathbf{)}$.

Find the number of ways person can climb

Let us use the recurrence relation $a_0=0a_1=0,a_n=2a_{n-1}+2a_{n-2}+3^{n-2}$to derive $a_7$ :

$$\begin{gathered} a_0=0 \\ {a}_1=0 \\ {a}_2=2a_1+2a_1+3^{2-2}=0+0+1=1 \\ {a}_3=2a_2+2a_1+3^{3-2}=2+2+3=5 \\ {a}_4=2a_3+2a_2+3^{4-2}=10+2+9=21 \\ {a}_5=2a_4+2a_3+3^{5-2}=42+10+27=79 \\ {a}_6=2a_5+2a_4+3^{6-2}=158+42+81=281 \end{gathered}$$$$\begin{gathered} a_0=0 \\ {a}_1=0 \\ {a}_2=2a_1+2a_1+3^{2-2}=0+0+1=1 \\ {a}_3=2a_2+2a_1+3^{3-2}=2+2+3=5 \\ {a}_4=2a_3+2a_2+3^{4-2}=10+2+9=21 \\ {a}_5=2a_4+2a_3+3^{5-2}=42+10+27=79 \\ {a}_6=2a_5+2a_4+3^{6-2}=158+42+81=281 \end{gathered}$$

Thus, there are 281 ways this person can climb a flight of eight stairs.