Why is the number of states for DFA is 3n + 1 for this language I'm taking online compilers course. It's long ended, so it wouldn't be cheating to ask a question on quiz here.

Let $S_i$ be the string consisting of $i$ 0's followed by $2i$ 1's. Define the language 
$L_n = \{ S_i | 1 \leq i \leq n \}$. For example,

$L_3 = \{\, 011,\, 001111,\, 000111111\; \}$

For any given $n$, what is the smallest number of states needed for a DFA that recognizes $L_n$?

I know regexes a bit and I can't think of a way of expressing this with regular expression. But I thought even if it's possible it should involve some kind of backreference, and isn't backtracking impossible with DFA?

So the quiz gives the correct answer $3n + 1$ and explain it like so.


  We need states to count how many 0 we meet and how many 1 we meet, so we need 3*n+1 states including the start state.


And this explanation doesn't explain anything to me. I mean okay the $+1$ part obvious, but why is there $3n$? I mean I agree that we probably need states to count how many 0 and 1 we meet, but exactly how we're gonna do it? If anything we should have 4 states in my opinion. One recognize 0, one to recognize 1 and another two states to count the numbers of them.

Right now I'm reading articles and papers about NFA, DFA, regular expressions and backreference, but maybe the answer is much simpler?

EDIT1.
Okay, I've tried my best and constructed kind of obvious DFA for this task.


The total number of states would be $\sum_{i=1}^{n}i+2i$ which looks like arithmetic progression to me with a difference $d=(i+1)+2(i+1)-(i-2i)=i+1+2i+2-i-2i=3$ So the sum will be equal to $\frac{n(a_1 + a_n)}{2}=\frac{n(3 + (n + 2n))}{2}=\frac{n(3+3n)}{2}=\frac{3(n^2+1)}{2}$

I don't see $3n + 1$ here.

Okay, I think I finally got this. The main problem I think was that I haven't tried to actually draw automaton initially and If I would it would be much easier. So once I've noticed that it could be changed into this

And this would give $3n+1$ obviously.
This is indeed a curious example. The reason why it works is the following (I show you on the example of $L_3$, but the argument is generic).
Start with the minimal DFA accepting $\{S_n\}$, which clearly has $|S_n| + 1 = 3n + 1$ states. The states can be encoded by factorisations of $S_n$ in two factors (the reason of this encoding will appear shortly). Thus for $S_3$ you get
$$
  (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{0} (00, 0111111) \xrightarrow{0} (000, 111111) \xrightarrow{1} (0001, 11111) \xrightarrow{1} (00011, 1111) \xrightarrow{1} (000111, 111) \xrightarrow{1} (0001111, 11) \xrightarrow{1} (00011111, 1) \xrightarrow{1} (000111111, \varepsilon)
$$
Now it is possible to accept the words $S_i$ by adding new transitions (but no new state!). For instance, if you want to accept $011$, you add the transition $(0, 00111111) \xrightarrow{\color{red}{1}}(00011111, 1)$ to get
$$
  (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{\color{red}{1}}(00011111, 1) \xrightarrow{1} (000111111, \varepsilon)
$$
and to accept $001111$, you add the transition $(00, 0111111) \xrightarrow{\color{red}{1}}(000111, 111)$ to get
$$
(\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{0} (00, 0111111) \xrightarrow{\color{red}{1}}(000111, 111) \xrightarrow{1} (0001111, 11) \xrightarrow{1} (00011111, 1) \xrightarrow{1} (000111111, \varepsilon)
$$
The trick is that you still get a deterministic automaton, due to the choice of the words added to the original automaton.