On partitioning of $F_2^n$ I was solving a problem in Nielsen and Chuang's book on quantum computing. To solve it, I had to use the following result:
Define the inner product between binary vectors $a,b \in \mathbb{F}_2^n$ as
\begin{equation}
\langle a, b\rangle = \sum_{i=1}^n a_i.b_i \mod 2
\end{equation}
Suppose $b$ is fixed as a non-zero vector, then show that the function $f(x) = \langle x, b\rangle$ for $x \in \mathbb{F}_2^n$ is $0$ for half the possible inputs and $1$ for the other half. I couldn't find this problem on Mathstack possibly because of poor wording. If this has been solved before, kindly point me to the link.
I tested this out for several test cases and I found it to be true. I figured it had to do with the periodicity of the positions when the input sequences are written one below the other. But I'm having trouble writing out a formal proof. I appreciate any clarity I can get in this. If this problem has been solved before on Mathstack, kindly point me in the right direction.
For those who know of Deutsch Josza algorithm, $f$ is called a balanced function.
 A: First let's consider the cases where $b_i=1 \forall 1 \leq i \leq n$. Then you want to count the number of binary vectors $a$ such that $\Sigma a \equiv 0 \mod 2$. Notice that's equal to choosing even number of bits from the $n$ bits available i.e.
$$\Sigma_{k=0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k}$$ which is $2^{n-1}$, half of the possible choices.
Now to solve the general case, notice that when you add a $0$ to the vector $b$, both the number of odd cases and even cases double, and the total cases double as well. Therefore, the ratio doesn't change, and half of all $a$ choices will give $f(x) = 0$ 
Cheers! :) 
A: First, given $b\not=0$ there exists a vector $b'$ such that$\langle b',b\rangle=1$. To see this let $b'$ coincide with $b$  in one place where $b$ takes value $1$, and otherwise be $0$.
Now $f: x\mapsto\langle x,b\rangle$ is a linear map from the vector space $\mathbb{F}_2^{n}$ to the one-dimensional space $\mathbb{F}_2$; and by our first remark it is onto.
By the rank-nullity theorem the kernel of $f$ has dimension $(n-1)$ so that $2^{n-1}$ elements map to $0$; the other $2^{n-1}$ elements map to $1$. 
