I need to find a good approximation of $S_n$ for big n's.
$S_n = \sum_{i=0}^n \frac{n!}{i!(n-i)!}{2^{-n}}\log_2\frac {n!}{i!(n-i)}.$
I've computed this sum using Python on $1\leqslant n\leqslant500$ using increments of 10 and got these results: Results plotted to a graph
It resembles a line but as n gets larger the deviation from x=y gets larger as well. What's the best approximation equation I can get for this without computing the sum itself?
I'll work in base-e, not base-2 and assume the proposer can convert appropriately. The following asymptotic expansion holds: $$T_n := 2^n\sum_{k=0}^n \binom{n}{k} \log{\Big(\binom{n}{k}\Big) } \sim n\log{2} -\frac{1}{2}\log{n} + \frac{1}{2}\Big(\log{\frac{2}{\pi}} -1 \Big) $$ For an example of the precision, for n=20 the brute force summation gives 11.6395 and the approximation gives 11.6393.
This one is easy because the summand is not oscillating and the binomial is strongly peaked near the center of the summation range. Therefore use the approximation $$ \binom{n}{k} \sim \binom{n}{n/2} \exp{\big(-\frac{2}{n}\big(\frac{n}{2}-k\big)^2 \Big)} $$ but use it only within the logarithm. Therefore $$ T_n \sim 2^{-n} \sum_{k=0}^{n} \binom{n}{k} \Big( \log{\Big( \binom{n}{n/2} \Big) } -\frac{2}{n}(\frac{n}{2} - k)^2 \Big) = $$ $$ = 2^{-n}\Big( 2^n \log{\Big( \binom{n}{n/2} \Big) - \frac{2}{n} \cdot n \, 2^{-2+n} \Big)} $$ The first explicit sum is the binomial theorem, and the second can be derived from differentiating the binomial theorem twice and simplifying. The expression at the top of the answer comes from Stirling's approxiomation for the central binomial, and with algebra.