[JohanPerez]

Hola, debo resolver la siguiente proposición: Sea \( g(n) \) el número de maneras de escribr una cadena de unos y ceros, tal que nunca existen dos ceros sucesivos. Demuestre que \(  g(n)=fin(n+2) \).

Si tienen alguna idea de como puedo realizarlo se los agradezco enormemente.

Spoiler

Acá el enunciado en inglés por si perdió algo mi traducción: Let g(n) be the number of ways to write an string of n zeros and ones so that there are never two successive zeros. Show that g(n)=fin(n+2)

[cerrar]

[Abdulai]

Llamemos

\( Z(n) \)  Número de cadenas que terminan en 0
y
\( U(n) \)  Número de cadenas que terminan en 1

Cuyos valores iniciales son:  \( Z(1)=1 \)  y  \( U(1)=1 \)

Como no puede haber dos ceros consecutivos, los términos siguientes son:

\( Z(n)=U(n-1) \)               ; Porque la anterior debe terminar en 1
\( U(n)=U(n-1)+Z(n-1) \)   ; Porque la anterior puede terminar en 0 o 1

\( Z(1)=1 \)             
\( U(1)=1 \)   
\( Z(2)=U(1)=1 \)             
\( U(2)=U(1)+Z(1)=2 \)   
\( Z(3)=U(2)=2 \)             
\( U(3)=U(2)+Z(2)=3 \)   
...................................

Pero notemos que  \( U(n)=U(n-1)+Z(n-1)=U(n-1)+U(n-2) \)   es la sucesión de Fibonacci

Por definición  \( \text{Fib}(1)=1\quad\text{Fib}(2)=1 \) 
resultando 
\( U(n)=\text{Fib}(n+1) \)
\( Z(n)=\text{Fib}(n) \)


Como el número total de cadenas será la suma de las terminadas en 0 y en 1

\( g(n)=U(n)+Z(n)=\text{Fib}(n+1)+\text{Fib}(n)=\text{Fib}(n+2) \)

[JohanPerez]

¡Oh! Muchas gracias. No creo que yo lo hubiese pensado.