How many of the 65536 possible shorts over Z2 have no two consecutive symbols the same? [closed]

Probability-related Info theory question that I can't figure out. Thanks in advance!

• Please edit your question to clarify what you are asking (what do you mean by "shorts over Z2", and by symbols), to show us what you've tried and where you got stuck. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. – D.W. Sep 21 '16 at 5:28

I assume you are talking about the binary digits of all nonnegative integers < $2^{16}$.

The first binary digit of any positive integer must be $1$, because otherwise it's a leading zero and that means we're counting numbers twice. However, if we do not want two consecutive digits to be the same, this uniquely determines the rest of the bits, because they must alternate: $1010101...$.

So for $b > 1$, there exists exactly one $b$-bit integer with no consecutive binary digits.

For $b = 1$ there are two strings: $0$ and $1$.

Thus, if we are interested in the number of integers below $2^{16}$ without consecutive digits, there is one 16-bit number, one 15-bit, .. one 2-bit and two 1-bit numbers. So the answer is 17.

For completeness' sake, here they are:

0 = 0
1 = 1
2 = 10
5 = 101
10 = 1010
21 = 10101
42 = 101010
85 = 1010101
170 = 10101010
341 = 101010101
682 = 1010101010
1365 = 10101010101
2730 = 101010101010
5461 = 1010101010101
10922 = 10101010101010
21845 = 101010101010101
43690 = 1010101010101010