Expected earliest point at which a sock matches an earlier sock The University of Waterloo CEMC's Problem of the Month for November, the problem statement for which can be seen here, was authored by me. (As far as I know, it is original, though I have come to expect that such low hanging fruits have already been plucked. Forgive me if someone authored a similar problem earlier.)
In essence, I was inspired by the fact that I had $n$ pairs of matching socks in a laundry bag and I was pulling socks out one at a time and hoping that, at some point, I would obtain a sock that matched a previously drawn sock (this was before I had degenerated to the point that I did not care about my socks matching). The main part of the problem asks for the pulled sock number $k+1$ at which the probability is highest that the earliest match occurs. The official solution can be read here and it interestingly has to do with triangular numbers.
Given $2n$ total socks (so $n$ pairs of matching socks), the probability of the first match occurring upon removing the $(k+1)^{\text{th}}$ sock for $1\le k\le n$ is $$P(n,k) = \frac{k2^k n! (2n-k-1)!}{(2n)!(n-k)!}.$$ For those wondering, this probability is the same regardless of whether the socks within a single pair are distinguishable or indistinguishable, though in reality, they are of course indistinguishable.
This means the expected sock number at which the first match occurs is $$E(n)=\sum_{k=1}^{n}{k\cdot P(n,k)} = \sum_{k=1}^{n}{\frac{k^2 2^k n! (2n-k-1)!}{(2n)!(n-k)!}}.$$
According to Wolfram Alpha, the first $9$ values of this function are: $$1,\frac{5}{3},\frac{11}{5},\frac{93}{35},\frac{193}{63},\frac{793}{231},\frac{1619}{429},\frac{26333}{6435},\frac{53381}{12155}.$$
Does it seem to grow like a square root? I'm not sure.
My question is: Can this expected value function be written in a closed form, or be approximated by bounds or by an asymptotic formula?
 A: First of all, your "expected sock number" is $1$ off, because $P(n,k)$ is the probability for the $(k+1)^{\text{th}}$ sock. I am making this correction because the formula when you add $1$ is nicer. So I will give a formula for the sequence $$2, \frac83, \frac{16}{5}, \frac{128}{35}, \dots$$ which is shifted by $1$ from your sequence. (Just looking at this might lead you to some guesses about what the formula is!)
It is often easier to compute the expected value of a
(nonnegative integer-valued) random variable $\mathbf X$ by the formula
$$
   \mathbb E[\mathbf X] = \sum_{k \ge 0} \Pr[\mathbf X > k].
$$
(You can check that $\Pr[\mathbf X = k]$ is counted exactly $k$ times in this sum.) In this case, $\Pr[\mathbf X > k]$ is the probability that the first $k$ socks are all different. This has a nicer formula: $$\Pr[\mathbf X > k] = \frac{\binom{n}{k} 2^k}{\binom{2n}{k}} = \frac{n!(2n-k)!2^k}{(2n)!(n-k)!} = \frac{\binom{2n-k}{k}2^k}{\binom{2n}{n}}.$$ So we now want to evaluate the sum
$$
   \mathbb E[\mathbf X] = \frac{1}{\binom{2n}{n}} \sum_{k=0}^n \binom{2n-k}{n}2^{k}.
$$
This sum has a combinatorial interpretation: $\binom{2n-k}{n}2^{k}$ is A276418, the number of paths of length $2n$ that start at $0$, go up or down at each step, and return to $0$ exactly $k$ times. (I don't know if there's an easy argument that counts these.) Summing these over all $k$ gives $4^n$: the number of paths of length $2n$ that start at $0$ and go up or down at each step.
Therefore $\mathbb E[\mathbf X] = 4^n/\binom{2n}{n}$. Asymptotically as $n \to \infty$, $\mathbb E[\mathbf X] \sim \sqrt{\pi n}$.
