Probar que la función es la secuencia de Fibonacci

Question

Atascado en la forma y para terminar una pregunta yo estoy trabajando. Tiene que encontrar el número de bitstrings de longitud n con ningún extraño longitud máxima de las carreras de. Por ejemplo, cuando n=3 hay tres bitsrings: 011, 110 y 000. He averiguado n=1 no es 1, n=2 hay 2, n=3 hay 3, n=4 hay 5, y cuando n=5 hay 8 y así sucesivamente. Esta es claramente la secuencia de Fibonacci. Mi problema es que no sé cómo demostrar que el número de estos bitstrings de longitud n es igual al número de estos bitstrings de longitud n-1 más el número de estos bitstrings de longitud n-2.

Larga historia corta, ¿cómo puedo demostrar que el resultado de una función es la secuencia de Fibonacci?

Gracias por la ayuda!!

Answer 1

Deje $S_n$ ser este número de $n$ longitud de la cadena de bits. A continuación, se observa que la $S_{n+1}$ se componen de cadenas de bits obtenida después de anexar $0$ o $1$ antes de la $n$ de la longitud de cadenas de bits. Por eso, $S_{n+1}$ cadenas de bits contendrá la $S_n$ $n$ la longitud de cadenas de bits que se anexa $0$ y también contendrá los $n$ de la longitud de cadenas de bits que tiene una extraña carrera de $1$s a partir de su MSB y los que no contienen impar ejecutar más adelante en la cadena de bits. Esto claramente significa que estos $S_{n+1}-S_n$ $n$ la longitud de cadenas de bits son el resultado de anexar $1$ antes de la MSB de todas las $n-1$ de la longitud de cadenas de bits con ninguna longitud impar de ejecución de $1$'s decir $S_{n+1}-S_n=S_{n-1}$.

Answer 2

Decir que una cadena de bits es buena si no tiene de longitud impar máximo de ejecución de aquellos. Deje $a_n$ el número de cadenas de longitud $n$. Supongamos que $\sigma$ es una buena cadena de longitud $n$. Si $\sigma=\tau0$ donde $\tau$ es la subcadena que consta de la primera $n-1$ bits de $\sigma$, $\tau$ es una buena cadena de longitud $n-1$. Por el contrario, si $\tau$ es buena cadena de longitud $n-1$, $\tau0$ es una buena cadena de longitud $n$ terminando en $0$. Por lo tanto, el número de cadenas de longitud $n$ terminando en $0$$a_{n-1}$.

Ahora supongamos que $\sigma$ termina en $1$. A continuación, $\sigma$ debe terminar en $11$ (por qué?), por lo $\sigma=\tau11$ para algunos cadena de $\tau$ de la longitud de la $n-2$. Por otra parte, $\tau$ debe ser bueno; ¿por qué? Por el contrario, si $\tau$ es una buena cadena de longitud $n-2$, $\tau11$ es una buena cadena de longitud $n$ terminando en $1$. Por lo tanto, el número de cadenas de longitud $n$ terminando en $1$$a_{n-2}$. Hemos cubierto todas las posibilidades, por lo $a_n=a_{n-1}+a_{n-2}$.