Tengo $F_n$ número de cadenas de bits que tienen $000$ ¿Cómo puedo demostrar que $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$ ? Ahora hay muchas maneras de ir sobre esto pero si elijo comenzar un $n-3$ y añadirle $000$ ¿cómo lo demostraría?
Respuestas
¿Demasiados anuncios?
Oli
Puntos
89
Sea $G_n$ sea el número de picaduras de bits de longitud $n$ que tienen no $000$ . Encontraremos una recurrencia para $G_n$ y utilizarlo para obtener una recurrencia para $F_n$ . La última parte será relativamente fácil, ya que $F_k+G_k=2^k$ .
Es útil introducir una abreviatura informal. Llamar a una cadena de bits mal si no tiene $000$ .
Sea $n\ge 4$ . Una cadena mala de longitud $n$ puede comenzar con $1$ . Existen $G_{n-1}$ cadenas defectuosas, ya que añadir cualquier cadena defectuosa de longitud $n-1$ a $1$ hará el trabajo.
Una cadena incorrecta puede empezar por $01$ . Existen $G_{n-2}$ cuerdas tan malas.
Una cadena incorrecta puede empezar por $001$ . Existen $G_{n-3}$ cuerdas tan malas.
¡Eso es todo! Así que $$G_n=G_{n-1}+G_{n-2}+G_{n-3}.$$ De ello se deduce que $$2^n-F_n=(2^{n-1}-F_{n-1})+(2^{n-2}-F_{n-2})+(2^{n-3}-F_{n-3}).$$ Esto se puede transformar en $$F_n=F_{n-1}+F_{n-2}+F_{n-3}+2^{n}-2^{n-1}-2^{n-2}-2^{n-3}.$$ Pero $2^{n}-2^{n-1}=2^{n-1}$ y $2^{n-1}-2^{n-2}=2^{n-2}$ y $2^{n-2}-2^{n-3}=2^{n-3}$ . Concluimos que $$F_n=F_{n-1}+F_{n-2}+F_{n-3}+2^{n-3}.$$
Florian Feldhaus
Puntos
138
También puedes utilizar el desglose positivo. Considere el primer bit como 1 o 0. Para uno, no hay resultados adicionales y se obtiene $a_{n-1}$ . Para 0, se obtiene un conjunto extra de casos en los que los 3 primeros son cero, lo que ocurre $2^{n-3}$ veces. Repitiendo el proceso para la segunda y tercera cifras - sin añadir los casos ya contados en $2^{n-3}$ - y obtienes el resto del argumento que se te pidió que probaras.
También se puede demostrar por inducción (Caso base n=4)
