Find number of solutions of $x_1 \wedge x_2 \oplus x_2 \wedge x_3 \oplus ... \oplus x_{n-1} \wedge x_n = 1$ I'm trying to find number of solutions of boolean equation $$x_1 \wedge x_2 \oplus x_2 \wedge x_3 \oplus ... \oplus x_{n-1} \wedge x_n = 1$$
where $\oplus$ is Exclusive or and $\wedge$ is Logical conjunction
My knowledge of combinatorics is not good enough, so my first idea was to code a program which produces correct output for further investigation.
And the output was something like this
n = 2   counter: 1
n = 3   counter: 2
n = 4   counter: 6
n = 5   counter: 12
n = 6   counter: 28
n = 7   counter: 56
n = 8   counter: 120
n = 9   counter: 240
n = 10  counter: 496
n = 11  counter: 992
n = 12  counter: 2016
n = 13  counter: 4032
n = 14  counter: 8128
n = 15  counter: 16256
n = 16  counter: 32640
n = 17  counter: 65280
n = 18  counter: 130816
n = 19  counter: 261632
n = 20  counter: 523776

After some googling, I came out with this sequence
I'm really interested about how can I solve this problem by some "counting" methods. Here's the program I wrote in case you're interested about the output (hope it is correct).Thanks for your help.

For each assignment of values to $x_1,\ldots,x_n$ we get in induced subgraph of the path graph $P(n)$ on vertices $1,\ldots,n$: specifically, we get the subgraph that has an edge $\{k,k+1\}$ iff $x_k\land x_{k+1}=1$. Then $\bigoplus_{k=1}^{n-1}(x_k\land x_{k+1})=1$ iff the corresponding induced subgraph has an odd number of edges. In view of the COMMENTS section of OEIS A032085, this shows that we really are dealing with that sequence. Thus, if $a_n$ is the number of solutions for $n$ variables, the sequence satisfies the recurrence
$$a_n=6a_{n-2}-8a_{n-4}$$
for $n\ge 6$ with $a_2=1,a_3=2,a_4=6$, and $a_5=12$. 
This is really just two interlaced instances of the recurrence $b_n=6b_{n-1}-8b_{n-2}$, one with initial values $b_1=1$ and $b_2=6$, and the other with initial values $b_1=2$ and $b_2=12$. The auxiliary equation for this recurrence is $x^2-6x+8=0$, with zeroes $2$ and $4$, and it’s easy to check that the initial values $b_1=2$ and $b_2=12$ yield the solution $b_n=4^n-2^n$. The initial values $b_1=1$ and $b_2=6$, being half as large, must then yield the solution 
$$b_n=\frac12\left(4^n-2^n\right)=2^{n-1}\left(2^n-1\right)\;.$$
In terms of the original sequence we have
$$\left\{\begin{align*}
a_{2k}&=2^{k-1}(2^k-1)=2^{2k-1}-2^{k-1}\\
a_{2k+1}&=4^k-2^k\;.
\end{align*}\right.$$
These can be combined as
$$a_n=2^{n-1}-2^{\left\lfloor\frac{n-1}2\right\rfloor}\;.$$
