Proving that for the class of i.i.d. processes $R_n^*=\frac{k-1}{2}\log n + O(1)$ Let $\mathcal{P}$ be the class of i.i.d. processes on $A^\infty$ where $A = \{ 1, \dots, k \}$, and let $Q$ be the coding process treated in class,
$$Q(x_1^n)=\frac{\prod_{i=1}^k [(n_i-\frac{1}{2})(n_i-\frac{3}{2}) \cdots \frac{1}{2}]}{(n-1+\frac{k}{2})(n-2+\frac{k}{2})\cdots \frac{k}{2}},$$
where $n_i$ is the number of occurrences of symbol $i$ in $x_1^n$ (the product in the numerator is defined to be $1$ if $n_i = 0$.)
I would like to prove that
$$\frac{\prod_{i=1}^k(\frac{n_i}{n})^{n_i}}{Q(x_1^n)}$$
is bounded both above and below by a constant (depending on the alphabet size $k$ only) times $n^{\frac{k-1}{2}}$ and thus concluding that for the class of i.i.d. processes $R_n^*=\frac{k-1}{2}\log n + O(1)$.
I tried rewriting $Q(x_1^n)$ using
$$(n-\frac{1}{2})(n-\frac{3}{2})\cdots \frac{1}{2} = \frac{(2n)!}{2^{2n}n!}$$
in terms of factorials (regarding the denominator, distinguishing the cases $k=$ odd and $k=$ even), then applying Stirling’s formula
$$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12(n+1)}}\leq n!\leq \sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n}}.$$
 A: I'm going to explicitly assume $k \le 2n$. Since you're arguing in the regime $n = \omega(1), k = \Theta(1),$ this asymptotically holds. 
This is essentially an exercise in judiciously using Stirling's approximation, and being nice to oneself by hiding factors that don't matter.

The numerator of $Q$ is $ N:= \prod_{i= 1}^k \frac{(2n_i)!}{4^{n_i} n_i!} $ by the expression you have. Using Stirling's approximation in the form you have, we can further bound the terms as $$ \frac{1}{C'}n_i^{n_i} e^{-n_i} \le  \frac{(2n_i)!}{4^{n_i} n_i!} \le C \frac{(2n_i)^{2n_i + 1/2} e^{-2n_i}}{4^{n_i} n_i^{n_i + 1/2} e^{-n_i}} = C' n_i^{n_i} e^{-n_i},$$
where $C, C'$ are some absolute constants. This tells us that $$ N \asymp e^{-n} \prod n_i^{n_i},$$ where by $\asymp$ I mean equal up to factors depending only on $k$.
Simlarly let $D$ be the denominator of $Q$. Since we don't care about $k$-dependent factors, note that we can increase the demoninator to just $(n-1 + k/2)!$ if $k$ is even, or to $(n-1+k/2) \dots 1/2$ if $k$ is odd. For even $k$, then, $$D \asymp (n-1 + k/2)^{n + (k-1)/2} e^{-n} = (n + \lfloor (k+1)/2 \rfloor-1)^{n + (k-1)/2} e^{-n}$$
While for odd $k$, we instead have the expression $$ D \asymp (n + (k-1)/2 - 1/2) \dots 1/2 = \frac{ (2n + k-1)!}{4^{n + (k-1)/2} (n +(k-1)/2)!}\\ \asymp (n + (k-1)/2)^{n + (k-1)/2} e^{-n} = (n + \lfloor (k+1)/2 \rfloor -1)^{n + (k-1)/2} e^{-n}.$$ 
So, $$Q \asymp \frac{\prod n_i^{n_i}}{ (n + \lfloor (k+1)/2 \rfloor-1)^{n + (k-1)/2}} = \frac{\prod (n_i/n)^{n_i}}{n^{-n} (n + \lfloor (k+1)/2 \rfloor -1)^{n + (k-1)/2}}.$$
So the conclusion will  follow if $$ (n+ \lfloor (k+1)/2 \rfloor-1)^{n + (k-1)/2} \asymp n^{ n + (k-1)/2}.$$
To see this, note that the ratio of these is $$ 1 \le \left(1 + \frac{\lfloor (k+1)/2 \rfloor -1}{n}\right)^{n + (k-1)/2} \le \exp\left( \frac{k}{n} (n + (k-1)/2)\right) \le \exp(2 k)$$
under the assumption $k \le 2n.$ But these bounds are only $k$ dependent, so the ratio is $\asymp 1$ as needed.
