Proof for minimum number of states for a epsilon free NFA is $2^n$ I have the following question which I could not proceed:
Let 
$$L=\{w \in \Sigma^*  \mid \text{all symbols of the alphabet occur even times in } w\}.
$$
Prove that any NFA accepting $L$ requires $2^n$ states, where $n$ is the size of the alphabet $\Sigma$. 
I think I came up with a proof for a DFA using the Myhill-Nerode Theorem but I do not know how to generalize it to NFA's. 
Edit:Relevant question is answered in https://stackoverflow.com/questions/9068873/how-do-we-know-that-an-nfa-has-a-minimum-amount-of-states .
 A: The answer to the relevant question refers to
a theorem of [1] that can be used to determine lower bounds on the number of states of a minimal NFA:

Theorem. Let $L \subseteq \Sigma^*$ be a regular language and suppose that there exist $n$ pairs of words $P = \{(u_i, v_i)  \mid 1 \leqslant i \leqslant n \}$ such that:

*

*$u_iv_i \in L$ for $1 \leqslant i \leqslant n$

*$u_jv_i \notin L$ for $1 \leqslant i,j \leqslant n$ and $i \not= j$.

Then any NFA accepting $L$ has at least $n$ states.

Suppose that $\Sigma = \{a_1, \dots, a_n\}$. For each $i = (i_1, \dots, i_n) \in \{0, 1\}^n$, let $u_i = v_i = a_{i_1}^{i_1} a_{i_2}^{i_2} \dotsm a_{i_n}^{i_n}$. By construction, $u_i$ and $v_i$ satisfy the conditions (1) and (2). Since $|\{0, 1\}^n| = 2^n$, any NFA accepting $L$ has at least $2^n$ states.
[1] I. Glaister and J. Shallit, A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters 59 (2), pp. 75–77, (1996). DOI:10.1016/0020-0190(96)00095-6.
