Prueba de cadenas binarias (palabras)

Question

Estaba tratando de mejorar en las pruebas antes de los exámenes y me encontré con un problema, que no importa lo que intente, no tengo idea de cómo resolver:

Reglas para una palabra binaria válida:

1) No hay palabras de longitud 1
2) Las palabras de longitud 2 son "10" y "00" solamente
3) Si la palabra es más larga que 2, sólo es válida si se compone de una palabra válida más corta, de manera que los 1 se mantienen en el mismo lugar y TODOS los 0 se sustituyen por cualquier palabra válida (incluso la misma)

Demostrar, que el recuento total de palabras válidas para la longitud de palabra dada = n es igual a:

$$ \dfrac{2^{n}+2(-1)^n}3 $$

Se me ocurren algunos ejemplos:

Longitud de la palabra = 2:
Palabras válidas: 10, 00 (por definición); cuenta = 2

Longitud de la palabra = 3:
Palabras válidas: 110, 100; cuenta = 2

Longitud de la palabra = 4:
Palabras válidas: 1010, 1000, 0010, 1110, 0000, 1100; cuenta = 6

He intentado demostrarlo utilizando la inducción, pero todo lo que conseguí fueron ciclos inútiles. Incluso he escrito un programa sencillo para calcular todas las palabras posibles para la longitud dada, pero eso tampoco ayudó en absoluto.

Answer 1

Te daré algo de ayuda:

1) Una palabra válida anterior, sólo es fácilmente utilizable para producir parte del siguiente paso, si hay exactamente la diferencia de longitud de palabra número de 0's

2) Se deduce inmediatamente que sólo las palabras de longitud mayor o igual a $\lceil {n\over 2}\rceil$ son fácilmente utilizables.

3) Cada 0, puede ser sustituido por una palabra que empiece por un 1, o un 0 de longitud 2.

4) Por lo tanto, las palabras utilizables más pequeñas, producen la mayor parte del siguiente paso ( en el caso $n=5$ La longitud de la palabra 3 da 4 de las supuestas 10 sin recurrir al siguiente truco.

¡5) El truco es que cualquier palabra cuya longitud se sume al siguiente paso, puede reemplazar los 0 en 00 (en realidad se puede generalizar esto a cualquier cero duplicado en una palabra), Esto permite que la longitud de la palabra 3, produzca 8 palabras más usando esto! Pero algunas se repiten. (100,10,00)==(00,110,00) donde el primer argumento es una cadena a la que se le reemplazan sus 0, ordenando el resto por 0 su reemplazo.