Perceptron / logistic regression accuracy on the n-bit parity problem $\DeclareMathOperator{\sgn}{sign}$The perceptron (similarly, logistic regression) of the form $y=\sgn(w^T \cdot x+b)$ is famously known for its inability to solve the XOR problem, meaning it can get only to 75% accuracy.
I'm trying to understand what is its maximal accuracy on a generalized n bit XOR problem, which is the parity problem. The $n$ bit parity function returns, given a vector of $n$ bits, the parity of the number of 1 bits (0 if the number of 1 bits is even, 1 otherwise).
My initial hypothesis was that it should be $1/2+1/(2^n) $, meaning there we can correctly classify half of the points, plus one more.
However I was surprised to realize that the accuracy on the 3bit parity is 75% as well.
So for $n > 2$, empirically I'm getting $ 1/2 + 1/2^{(n-1)} $.
Is that true? What is the proof?
 A: This is not a complete answer but hopefully contains useful hints.
In the 2-bit case, there are three types of points, having $0$, $1$ or $2$ bits on. The four lines that achieve 75% accuracy with maximum margin are $x_0+x_1=\frac{1}{2}
$ and $x_0+x_1=\frac{3}{2}$, $x_0-x_1=\frac{1}{2}$ and $x_0-x_1=-\frac{1}{2}$.
With 3 bits, there are $1, 3, 3, 1$ points having $0, 1, 2, 3$ bits on. This is naturally represented in 3D space. A plane between the parallel planes described by the three-point sets classifies correctly $6$ points over $8$, $\frac{3}{4}$ as well.
In 4 bits, with point counts $1, 4, 6, 4, 1$, there is correct classification for $4+6+1$ points, $\frac{11}{16}$.
If the patterns continues the same way, the number of points classified correctly is $2,3,6,11,22,42,84,163,326,638,1276,2510,5020,9908,19816,39203...$
This conjectured sequence is not in the OEIS and has the following equation.
$$\sum_{k=0}^{n/2} \binom{n}{k} $$ for $k$ even,
$$\sum_{k=0}^{(n-1)/2} \binom{n-1}{k} $$ for $k$ odd.
Since the odd index values in the sequence are the double of their previous count and the accuracy is obtained dividing by $2^n$, the repetition observed in $2$ and $3$ bits (repeating accuracy $\frac{3}{4}$) follows for all even-odd pairs. For instance, $\frac{11}{16}$ is the accuracy obtained at $4$ and $5$ bits.
