Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states


How can you prove that any DFA accepting the language generated by the regular expression $ \{0|1\}^*0\{0|1\}^n$ requires at least $ 2^{n+1}$ states?

I first attempted induction on $ n$ . But I don’t even see how to prove the base-case, like if $ n=1$ . You need the DFA to take any string and, when it encounters a 0, get set down a track of checking that $ n$ characters follow. If it’s fewer than $ n$ then fine you reject. But if there are more characters, to sort of re-set it so that it looks for the first 0 after the earlier one was found. But DFAs don’t have that kind of memory.

And once you’ve established the base-case, the inductive case doesn’t seem clear either. If you know the result is true up to $ n$ , then if you consider the regex with $ n+1$ then you get a DFA which accepts it. You intuitively want to remove the accepting states and "move them back" one vertex in the graph. Now you have a DFA with at least $ 2^n$ states. But how do you know that you needed $ 2^n$ accepting states so that the net number of accepting states is then $ 2^{n+1}$ ?