Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states
This isn't about induction, it's about proving that the correct DFA must have enough memory to remember everything about the last $n+1$ characters. The very number $2^{n+1}$ should have been a clue to this.
Imagine that the DFA has just now read some prefix that's longer than $n+1$, but it doesn't yet know if there are any more characters left. Ask the question: what must the DFA currently remember?

Well, clearly, it must remember what it read $n$ characters ago, to decide whether to accept or reject if the string just ends right now
It also must remember what was $n-1$ characters ago, just in case the string ends 1 character later
And it must remember what was $n-2$ characters ago, just in case the string ends 2 characters later
And it must remember what was $n-3$ ...

As you can see, by that kind of logic it must be absolutely sure about each of $2^{n+1}$ bits. To formalize this deduction, try to prove the following:
LEMMA: If $a$ and $b$ are two different strings of length $n+1$, then they should lead the DFA in question to two different states.
The method for proving this lemma is to append things to $a$ and $b$, such that, for example, string $ac$ must be accepted and string $bc$ must be rejected. If the automaton knows the difference between $ac$ and $bc$, then it must have known the difference between $a$ and $b$. Look up &quot;right invariant equivalence&quot; if you don't already know that concept.
Once you prove the lemma, the rest is obvious. There are $2^{n+1}$ different strings which all lead to different states. Therefore, there are at least $2^{n+1}$ different states.