Why are the order statistics of uniform Beta?

For a beta distribution with parameters $a$ and $b$, we can interpret it as the distribution of the probability of heads for a coin we tossed $a+b$ times and saw $a$ heads and $b$ tails. At the same time, if we draw $n$ uniform random numbers and sort them, the $k$-th order statistic is also Beta distributed with parameters $a=k$ and $b=n+1-k$. So, its like we tossed $n+1$ coins and got $k$ heads. Is there an intuitive explanation for this? I can see the derivations mechanically but any logical reason the two distributions should be the same?

You answered your own question completely and entirely, using the observation by lee-david-chung-lin. Actually a Beta(a,b) distribution for $a,b \in \{1,2,\dots\}$ is the same as the Bayesian posterior for $U$ when $U$ is uniform, a priori, and we observe that the outcomes of a Binomial(U,n) random variable is $a-1$ for $n=(a-1)+(b-1)=a+b-2$. That is just because the density of a Beta(a,b) random variable is $x^{a-1}(1-x)^{b-1} \mathbf{1}_{[0,1]}(x)/B(a,b)$ where $B(a,b)$ is the Beta integral. But the probability for a binomial(n,p) random variable to equal $k$ is $\binom{n}{k} p^k (1-p)^{n-k}$. So changing $p$ to $x$, using Bayes's rule, and matching $a-1$ to $k$ and $b-1$ to $n-k$ gives the result. That is what was pointed out by lee-david-chung-lin. So then the $a$ for the $k$th order statistic is $a=k-1+1$ following your explanation Rohit Pandey and $b=n-k+1$. Those match the desired connection.

There is a trivial discrete analog. Imagine $L$ boxes in a linearly-ordered row, with $n$ balls in the boxes, such that there are no more than 1 ball in each of the boxes. The probability for the $k$th ball (reading left-to-right) to be in box $x$ is $\binom{x-1}{k-1} \binom{L-x}{n-k}/\binom{L}{n}$ for each possible choice of $x$. (Note that, summing over $x$, this generalizes the ``hockeystick identity'' for binomial coefficients in a trivial way.) This is not quite the same: here the primary interpretation is in terms of the $k$th order-statistics.

The binomial(n,p) distribution is replaced by a capture-recapture hypergeometric distribution, which is not as straightforward as the binomial. Imagine a population of $L-1$ elephants and you capture and tag a uniformly distribution random number $\mathsf{Y}$ elephants, and set $x=y+1$ if $\mathsf{Y}=y$. (This hypothesis is admittedly a bit odd in this context.) Then you randomly collect a new sample of $n-1$ of the elephant population. You discover $k-1$ of your new sample were tagged and $n-k$ were not. What is your updated guess for $y$?

This example is sometimes interesting in classes because it gives an explicitly calculable example for Bayes's rule that is purely discrete, setting it up just as you did Rohit Pandey for the continuous case. This could be a good example if one teaches basic probability to students who are concurrently learning multivariable calculus. Then you do not have to delay the Bayes' rule examples to the 2nd half of the semester. (For example, following Durrett's Elementary Probability for Applications [which is available free on his website now] but getting to this combinatorial Bayes' rule example before doing the multivariable calculus stuff in the later chapter on continuous distributions.)

I'm putting in a partial answer in the hope that either I or someone else will be able to fill in the missing pieces. At a high level, we can condition on the $k$-th order statistic. Then, all of the other samples of the uniform can lie either before it or after it. This becomes like tossing a coin and observing $n-k$ tosses are heads and $k-1$ are tails. This is off by one per the notation in the question and there might be a bug somewhere (like @LeeDavidChingLin suggested).