Finito de cadenas de bits que no contienen '$00$'

Question

Estoy estudiando para un examen y estoy teniendo problemas con esta cuestión de práctica:

En esta pregunta, consideramos finito de cadenas de bits que no contienen $00$. Ejemplos de tales bitstrings se $0101010101$$11110111$. Para cualquier entero $n\geq 2$, vamos a $B_n$ el número de bitstrings de longitud $n$ que no contengan $00$.

• Determinar el $B_2$$B_3$.
• Demostrar que $B_n = B_{n-1} + B_{n-2}$ por cada $n\geq 4$.
• Para cada una de las $n\geq 2$, expresar $B_n$ en términos de un número Fibonacci.

Cualquier ayuda es muy apreciada

Answer 1

$\textbf{Hint:}$La primera pregunta puede ser contestada por simplemente contar. Para la segunda pregunta tenga en cuenta que cada bitstring sin $00$ termina en cualquiera de las $1$ o en $10$. ¿Cuántas posibilidades hay en cualquiera de los casos? La tercera pregunta puede ser contestada por la combinación de los resultados de las dos primeras preguntas.

Answer 2

SUGERENCIA: Supongamos que tenemos una cadena de bits de longitud $n$. Consideran que el primer dígito de esta cadena de bits:

Si el primer dígito es $1$, es decir, tenemos $1xxxxxxxxxxxxx\ldots$ nuestra cadena de bits. ¿Cuántas posibilidades hay para el resto de $n-1$ dígitos?

Si el primer dígito es $0$, lo $\mathbf{must}$ el siguiente dígito? ¿Cuáles son las posibilidades para el resto de las $n-2$ dígitos?