¿Cuántos números binarios de longitud n no tienen ceros consecutivos? ¿Por qué obtenemos un patrón de Fibonacci?

Question

Posible duplicado:
Cuántos $N$ se pueden formar números binarios donde $0$ no se repite

Me da mucha vergüenza preguntar esto ya que parece una pregunta de libro de texto.Pero no lo es, y estoy completamente perdido en cómo conseguir un agarre en él.Se menciona en la primera conferencia de una serie de 24 conferencias sobre Matemáticas Discretas por el popular Sr.Arthur Benjamin(Matemáticas Discretas-Los Grandes Cursos), que estoy siguiendo. Sólo menciona fugazmente que usamos la combinatoria para resolverlo y que empezando con n=1 (número de 1 bit), la respuesta sigue el patrón de Fibonacci 2,3,5,8......Así que por favor, respondedme a esto para que no me desanime desde el principio del tema en sí.

i) Si se nos pide que encontremos el número de números binarios de longitud n sin ceros consecutivos, ¿cómo lo hacemos? Tengo una buena idea de combinatoria, coeficientes binarios, permutaciones, pero no sé cómo empezar.

ii)¿Por qué sigue un patrón Fibonacci para n,n+1,n+2 y así sucesivamente? Esto me desconcierta aún más.¿Por qué demonios se genera un patrón Fibonacci? Debe haber una explicación...

¡Tus respuestas, claras y fáciles de entender, me motivarán mucho para seguir profundizando en el tema.Gracias!

Answer 1

Considere la longitud $n$ cadenas binarias sin ceros repetidos (BSWNRZ).

BSWNRZ debe terminar en un $0$ o un $1$ . El número de BSWNRZ de longitud $n$ que terminan en un $0$ es igual al número de BSWNRZ de longitud $n-2$ (con $10$ anexo). El número de BSWNRZ de longitud $n$ que terminan en un $1$ es igual al número de BSWNRZ de longitud $n-1$ (con $1$ anexo).

Es decir, cualquier longitud $n$ BSWNRZ se encuentra en uno de los dos casos siguientes

$$ \overbrace{?????????????????}^{\text{any length }n-2\text{ BSWNRZ}}\color{#00A000}{1}\color{#C00000}{0}\\ \underbrace{??????????????????}_{\text{any length }n-1\text{ BSWNRZ}}\color{#C00000}{1} $$

Por lo tanto, el número de BSWNRZ de longitud $n$ es igual al número de BSWNRZ de longitud $n-1$ más el número de BSWNRZ de longitud $n-2$ . Así, el patrón de Fibonacci. $$ F_n=F_{n-1}+F_{n-2} $$