# Why is the function $f_s(x)=\sum_i x_i s_i \pmod 2$ balanced?

A parity function $$f_s:\{0,1\}^{n}\rightarrow\{0,1\}$$, for some $$s\in \{0,1\}^n$$, is a function of the form $$f_s(x) = x \cdot s$$, where the inner product is taken modulo 2.

Show that $$f_s$$ is a balanced function for all $$s$$

We have $$f_s(x) =\sum_i x_is_i \mod 2$$. If $$s \neq 0^n$$, then there exist $$i$$ such that $$s_i \neq 0$$. So, for all $$x$$, $$f_s(x) \neq f_s(x^i)$$, where $$x^i$$ the string obtained from by inverting bit $$i$$. Hence $$f_s$$ is balanced.

I really don't understand the second from last sentence. Why this does this imply the function is balanced?

Let's say that the first bit of $$s$$ $$s_0=1$$ (the argument will be exactly the same for any bit, just for convenience).
You can split the space of inputs $$x \in \{0,1\}^n$$ in two halves: one half where $$x_0 = 0$$ and the other half where $$x_0 = 1$$. For each bitstring $$x$$ from the first half you'll have a bitstring $$\tilde{x}$$ from the second half which will be equal to $$x$$ in all bits except the first one, and will differ from $$x$$ in the first bit.
Now consider $$f_s(x)$$ and $$f_s(\tilde{x})$$; you'll have $$f_s(x) = x_0s_0 + F$$ and $$f_s(\tilde{x}) = \tilde{x}_0s_0 + F$$ ($$F$$ is the sum of all terms except the first one). You know that $$x_0 = 0$$ and $$\tilde{x}_0 = 1$$, so you'll have $$F = f_s(x)$$ and $$f_s(\tilde{x}) = 1 + F$$, so you're guaranteed that $$f_s(x) \neq f_s(\tilde{x})$$.
This way you can split all possible $$x$$ in $$2^{n-1}$$ pairs, and each of the pairs will have different values of $$f_s$$ - which means that exactly $$2^{n-1}$$ values are 0 and $$2^{n-1}$$ are 1, and the function is balanced.