let $\Sigma = \set{a, b}$ and define the family of languages:

$$C_k = \setbuilder{x}{x \text{ has an } a \text{ in the } k \text{th position from the right end}}$$

Theorem: Any DFA recognizing $C_k$ must have at least $2^k$ states.

---

Proof: Consider the set of words $\Sigma^k$ and note that there are $2^k$ unique words in $\Sigma^k$. We will show that any DFA $M$ must take different strings in $\Sigma^k$ to different states.

Let $x, y \in \Sigma^k$ such that $x \neq y$. Write $x = x_1 x_2 \dots x_k$ and $y = y_1 y_2 \dots y_k$. Since they are unequal, let $d$ be the first index at which $x$ and $y$ differ. Then, between $x_d$ and $y_d$, one must be an $a$ and one must be a $b$. WLOG, suppose that $x_d = a$ and $y_d = b$ (otherwise, relabel $x$ and $y$).

Now, we want to construct new strings $x'$ and $y'$, adding characters at the end until $x'$ has its $a$ in the $k$th spot from the end, and $y'$ has its $b$ in the $k$th spot from the end. So let $x' = x \cdot a^{d-1}$ and $y' = y \cdot a^{d-1}$. Of course, we could have added $b$s to the end as well, the choice doesn't matter. Then $|x'| = |y'| = k + d - 1$, and the $kth$ index from the end is $(k + d - 1) - (k - 1) = d$. So, since $x_d = a$ and $y_d = b$, $x' \in C_k$ and $y' \not\in C_k$.

Now, notice that $\hat{\delta}(q_0, x') = \hat{\delta}(\hat{\delta}(q_0, x), a^{d-1}) \in F$, because $x'$ is accepted.

At the same time, $\hat{\delta}(q_0, y') = \hat{\delta}(\hat{\delta}(q_0, y), a^{d-1}) \not\in F$ because $y'$ is rejected.

If it were the case that $\hat{\delta}(q_0, x) = \hat{\delta}(q_0, y)$, then the same starting point and the same string $a^{d-1}$ would drive the machine to different states, which is a contradiction. So it must be the case that $\hat{\delta}(q_0, x) \neq \hat{\delta}(q_0, y)$.

So since each of the $2^k$ strings in $\Sigma^k$ must drive the machine to a unique state, $M$ must have at least $2^k$ states.