Discrete-Continuous Sequences

We solve the problem for sequences of length $n$ .

First, add a zero to the front and to the end of the sequence. Now write between each pair of successive digits whether they remain the same ( $\mathbf =$ ) or are different ( $\mathbf \star$ ). Thus, $(-1,0,0,1,1,0,1) \mapsto (0\ \mathbf \star\ {-1}\ \mathbf \star\ 0\ \mathbf =\ 0\ \mathbf \star\ 1\ \mathbf =\ 1\ \mathbf \star\ 0\ \mathbf \star\ 1\ \mathbf \star\ 0).$ It is easy to check that we have $n + 1$ symbols; and that the number of stars is even.

Consider the sequences with $2k$ stars (and $n + 1 - 2k$ equal signs). There are $\binom{n+1}{2k}$ ways to place the star. Every other star represents a jump from zero to either $+1$ or $-1$ . There are $2^k$ ways to choose these signs. Thus there will be $2^k\binom{n+1}{2k}$ sequences with $2k$ stars.

The total number of sequences is therefore $S(n) = \sum_{k=0}^{\lfloor (n+1)/2\rfloor} 2^k\binom{n+1}{2k}.$

It is not difficult to see, using the binomial theorem, that this may be written as $S(n) = \frac{(1+\sqrt 2)^{n+1} + (1-\sqrt 2)^{n+1}}2 = [\tfrac12(1 + \sqrt 2)^{n+1}].$ (Here, $[\cdot]$ stands for rounding to the nearest integer.)

---

For $n = 7$ , we find $S(n) = \binom 8 0 + 2\cdot\binom 8 2 + 4\binom 8 4 + 8\cdot\binom 8 6 + 16\cdot\binom 8 8 = 1 + 56 + 280 + 224 + 16 = 577;$ or $S(n) = [\tfrac12(1 + \sqrt 2)^8] = [576.99957] = \boxed{577}.$

---

Recursive solution

Let $S(n)$ be the number of sequences of length $n$ and $S_x(n)$ the number of these sequences ending in $x$ . Then $S_0(n) + S_{-1}(n) + S_{+1}(n) = 0;\ \ \ S_{-1}(n) = S_{+1}(n).$ We make a sequence of length $n$ by adding a digit to a sequence of length $n-1$ :

• if the original sequence ends in zero, we may any digit we wish (three possibilities); otherwise, there are only two valid choices: $S(n) = 3S_0(n-1) + 2(S_{-1}(n-1) + S_{+1}(n-1)) = S_0(n-1) + 2S(n-1);$
• to make a sequence ending in zero, we may start with any shorter sequence: $S_0(n) = S(n-1)$ .

Combining this, we see that $S(n) = S_0(n-1) + 2S(n-1) = 2S(n-1) + S(n-2).$ To solve this recursion equation, we try $S(n) = \alpha p^n$ and obtain $p^2 - 2p - 1 = 0$ . The solutions are $p = 1 \pm \sqrt 2$ ; thus we set $S(n) = \alpha(1 + \sqrt 2)^n + \beta(1 - \sqrt 2)^n,$ and with $S(0) = 1$ , $S(1) = 3$ we easily find $\alpha = \beta = \tfrac12$ .