Proving that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular I was asked to prove that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular. I can't solve this, could anyone help me?
This was an exam question from previous year. I looked your answers, but I can't really understand Yuval's solution and Matt's solution would be too long for an exam question.
From lecture we were given 3 methods to prove non-regularity. I thought that 3 methods are all classical methods to prove non-regularity, but it seems like the third one isn't so 'classical'.
The third one is as follows:

Let $\ L \subseteq (\Sigma_{bool})^* $ be a regular language.
Let $\ L_x=\{ y \in (\Sigma_{bool})^* | xy\in L \} $ for every$\ x \in (\Sigma_{bool})^*$. Then there exists a constant $\ c$, such that for all $\ x,y \in (\Sigma_{bool})^* $
$\ K(y) \leq \lceil log_2(n+1)\rceil+c $
if $\ y $ is the n-th word in the language $\ L_x $.

I'd like to show my proof using this method.

Suppose that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is regular.
We have ${2(n+1)}\choose{n+1}$ = ${2n \choose n+1}{2 \choose {0}} $ + ${2n \choose n}{2 \choose {1}}$ + ${2n \choose n-1}{2 \choose {2}}$.
i.e. ${2(n+1)}\choose{n+1}$ = $2*{2n \choose n}$ + ${2n \choose n+1}$ + ${2n \choose n-1}$  .        $(\ast)$
Then we define $\ L_n = L_{0^{{{2n}\choose{n}}+{{2n}\choose{n+1}}}}:=\{ y \in (\Sigma_{bool})^* | 0^{{{2n}\choose{n}}+{{2n}\choose{n+1}}}y\in L \} $ for every $n\in \mathbb{N} $.
Let $y_1$ be the first word in $L_n$. Obviously $y_1= $  $0^{{{2n}\choose{n}}+{{2n}\choose{n-1}}} $ by $(\ast)$. By the theorem,  there exists a constant $c$ ,such that for any $n \in \mathbb {N}$,
$\ K(y_1) \leq \lceil log_2(1+1)\rceil+c $.
Thus we can bound the Kolmogorov complexity of all elements in $S=\left\{0^{{{2n}\choose{n}}+{{2n}\choose{n-1}}} | n\in \mathbb {N}\right\}$ by constant $c$. However, this is an infinite set , we have only limited number of programs of length $\le c$. So we can't bound the Kolmogorov complexity of the elements in $S$, this means $L$ can't be regular.

If you don't know this theorem, you can find it here Proof of non-regularity, based on the Kolmogorov complexity. I don't know if my solution is right or not, if you find any problems please let me know.
A unary language (i.e., a subset of $0^*$) $L$ is regular iff the set $S = \{ n : 0^n \in L \}$ is eventually periodic. In particular, if $L$ is regular then either $S$ is finite or $S$ has positive density (in the following strong sense: $|S \cap [n]|/n$ converges to a positive number). However, in your case the set $S$ is infinite yet has density zero.

In the same way, we get that the following languages are not regular:
$$
\{0^{\lfloor n\log n \rfloor} : n \in \mathbb N\},
\{0^{n^2} : n \in \mathbb N\},
\{0^{2^n} : n \in \mathbb N\},
\{0^{n!} : n \in \mathbb N\}
$$
and so on.