This proof is from Introduction to Automata Theory Languages and Computation by Hopcroft & Ullman and is regarding a 'bad case' for subset construction (converting an NFA to a DFA).
The NFA which is being converted is as follows:
The argument for this then goes as follows:
Consider the NFA N of Fig. 2.15. $L(N)$ is the set of all strings of $0's$ and $1's$ such that the nth symbol from the end is $1$.
Intuitively, a DFA D that accepts this language must remember the last $n$ symbols it has read. Since any of $2^n$ subsets of the last $n$ symbols could have been $1$, if D has fewer than $2^n$ states, then there would be some state $q$ such that D can be in state $q$ after reading two different sequences of $n$ bits, say $a_1a_2…a_n$ and $b_1b_2…b_n$.
Since the sequences are different, they must differ in some position, say $a_i \neq b_i$. Suppose (by symmetry) that $a_i = 1$ and $b_i = > 0$. If $i = 1$, then q must be both an accepting state and a nonaccepting state, since $a_1a_2…a_n$ is accepted (the $n^{th}$ symbol from the end is 1) and $b_1b_2…b_n$ is not.
If $i > 1$, then consider the state $p$ that D enters after reading $i - 1$ $0$'s. Then p must be both accepting and nonaccepting, since $a_ia_{i+1}…a_n00…0$ is accepted and $b_ib_{i+1}…b_n00…0$ is not.
What's confusing me are these two lines,
Since any of $2^n$ subsets of the last $n$ symbols could have been $1$, ...
and
If $i > 1$, then consider the state $p$ that D enters after reading $i - 1$ $0$'s. Then p must be both accepting and nonaccepting, since $a_ia_{i+1}…a_n00…0$ is accepted and $b_ib_{i+1}…b_n00…0$ is not.
I understand the case where $i = 1$, but I don't understand how the $i \gt 1$ works, and what they mean by any of the $2^n$ subsets being $1$. How can the subsets be $1$?
You can ignore the first line you don't understand, that's just to give you some intuition.
For the case that $i > 1$, by assumption, after reading strings $a = a_1\cdots a_n$ and $b = b_1 \cdots b_n$, our DFA is in the same state. This means that for any string $q$, our automaton ends up in the same state after reading $aq$ as it does after reading $bq$. In particular, let $q$ be string consisting of exactly $i-1$ zeroes. Then, the automaton is in the same state for both $aq$ and $bq$, so it either accepts both or rejects both -- but that means that they have the same symbol as the $n$-th symbol from the end, which is not true: $n$-th symbol from the end in $aq$ is $a_i$, while $n$-th symbol from the end of $bq$ is $b_i$, and they are different.