Demostrar que el total de secuencias binarias de longitud n sin 1s consecutivos es Fib(n+1) .

Question

He visto múltiples posts sobre cómo probar esto, pero no entiendo por qué sólo necesitamos Fib(n-1) y Fib(n-2) de la serie Fib para demostrarlo. ¿Por qué sólo necesitamos Fib(n), Fib(n-1) y Fib(n-2)? ¿Cómo es que estos tres elementos de la serie son suficientes para decir secuencias totales de cadenas binarias válidas? ¿Por qué no podemos tener algo como Fib(n) = Fib(n - 1) + Fib(n - 2) + C*Fib(n-3) +...

Answer 1

Defina $a_n$ como el número de $n$ -secuencias que terminan en $1$ y $b_n$ el número de $n$ -secuencias que terminan en $0$ . Es fácil ver que $b_{n+1}=a_n+b_n$ y $a_{n+1}=b_n$ . De la segunda concluimos que $b_{n+1}=b_n+b_{n-1}$ y que define $$c_n:=b_n+a_n=b_{n+1}$$ concluimos lo que queremos.