I was trying to improve myself in proofs before the exams and came across a problem, that no matter what I try, I have no idea how to solve:
Rules for a valid binary word:
1) There are no words of length 1
2) Words of length 2 are "10" and "00" only
3) If the word is longer than 2, it is valid only if it is composed of a shorter valid word, in a way that 1s are kept on the same place and ALL 0s are each replaced with any valid word (even the same)
Prove, that the total count of valid words for the given word length = n equals to:
$$
\dfrac{2^{n}+2(-1)^n}3
$$
I've come up with a few examples:
Word length = 2:
Valid words: 10, 00 (by definition); count = 2
Word length = 3:
Valid words: 110, 100; count = 2
Word length = 4:
Valid words: 1010, 1000, 0010, 1110, 0000, 1100; count = 6
I've tried to prove it using induction, but all I achieved was worthless cycles.
I've even written a simple program to calculate all the possible words for the given length, but that also didn't help at all.
Best Answer
I'll give you some help:
1) A previous valid word, is only easily usable to produce part of the next step, if there are exactly the difference in word length number of 0's
2) It immediately follows that only words of length greater or equal to $\lceil {n\over 2}\rceil$ are easily usable.
3) Each 0, can be replaced with a word starting with a 1, or a 0 of length 2.
4) Therefore smaller usable words, produce most of the next step ( in the case $n=5$ word length 3 gives 4 of the supposed 10 without resorting to the next trick.
5) The trick is, any words whose lengths add to the next step, can replace the 0's in 00 ( you can actually generalize this to any doubled zero in a word), This allows word length 3, to produce 8 more words using this! But some are repeats. (100,10,00)==(00,110,00) where the first argument is a string getting its 0's replaced, ordering the rest by 0 its replacing.