An NFA with no equivalent DFA with fewer than $2^n$ states: Example and Proof

I have been following the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman.

I came across the following topic titled Bad Case for Subset Construction (2.3.6). I cannot follow the example given over there, about NFA N that can accept strings with 1 at the $n^{th}$ position, and that the DFA formed from that NFA thereafter will have no equivalent with fewer than $2^n$ states.


They argue that The DFA $D$ must be able to remember last n symbols it
has read. Since any of the $2^n$ subsets of the last n symbols could
be 1, if D had 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_{1}a_{2}...a_{n}$, and $b_{1}b_2...b_n$.

Here is an extract from the book itself:

I have been trying to comprehend the proof, including this line and the subsequent paragraph that follows, but I have not been able to.

Can someone please explain the approach ?

The proper way to do this proof is using Myhill–Nerode theory, which I will now explain. For a regular language $L$, say that $x,y$ are inequivalent if there exists a word $z$ such that $xz \in L$ and $yz \notin L$, or such that $xz \notin L$ and $yz \in L$. In every DFA accepting $L$, the state that is reached after reading $x$ is different from the state that is reached after reading $y$ (exercise). Hence, if we find a collection $x_1,\ldots,x_M$ of words such that $x_i,x_j$ are inequivalent for all $i \neq j$, then every DFA for $L$ must contain at least $M$ states (exercise).

For your language $L = \Sigma^* 1 \Sigma^{n-1}$, you can take as your collection of words the set of all words of length $n$. If $x,y$ are two different words of length $n$ then $x_i \neq y_i$ for some $i$; say $x_i = 0$ and $y_i = 1$. Then $x 0^{i-1} \notin L$ (since the $n$th from last bit is $x_i$ = 0), whereas $y 0^{i-1} \in L$ (since the $n$th from last bit is $y_i$ = 0). This completes the proof.

StackExchange Computer Science Q#54840, answer score: 5