0
$\begingroup$

I am trying to find an approximate expression for the following formula $$f(m) = 2^m \binom{\frac{n+m}{2}}{m}\binom{n+m}{m}^{-1},$$ where $n$ is fixed and large and $n+m$ are integers with the same parity (both even or odd) and $m = 0,\ldots, n$. When I plot it for $n=400$ it looks like a Gaussian function centered at $m=0$ with $\sigma = \sqrt{n}$. Any idea how to analytically find the approximate formula for large $n$?

$\endgroup$
1
$\begingroup$

Allright, let's see. We'll use ${i\choose j}=\frac{i!}{j!(i-j)!}$. This makes:

\begin{align} f(m)&=2^m \binom{\frac{n+m}{2}}{m}\binom{n+m}{m}^{-1}\\ &=2^m\frac{((n+m)/2)!}{m!((n-m)/2)!}\cdot\frac{m!n!}{(m+n)!}\\ &=2^m\frac{((n+m)/2)!n!}{(m+n)!((n-m)/2)!} \end{align}

Since $n!\sim n^ne^{-n}\sqrt{2\pi n}$ by Stirling's Approximation, we can substitute that to approximate $f(m)$;

\begin{align} f(m)&=2^m\frac{((n+m)/2)!n!}{(m+n)!((n-m)/2)!}\\ &\approx 2^m\frac{((\tfrac12(n+m))^{(n+m)/2}e^{-(n+m)/2}\sqrt{\pi (n+m)}n^ne^{-n}\sqrt{2\pi n}}{((n+m)^{n+m}e^{-n-m}\sqrt{2\pi (n+m)}((\tfrac12(n-m))^{(n-m)/2}e^{-(n-m)/2}\sqrt{\pi (n-m)}}\\ &=\frac{n^n\sqrt{n}}{(n+m)^{(n+m)/2}(n-m)^{(n-m)/2}\sqrt{n-m}}\\ &=\sqrt{\frac{n^{2n+1}}{(n+m)^{n+m}(n-m)^{n-m+1}}} \end{align}

We can see a lot gets cancelled. I don't think we can simplify this even further.

If you wish though, you can create an upper and lower bound using this exact method; since we have $\sqrt{2\pi}\cdot\sqrt{n}n^ne^{-n}\leq n!\leq e\cdot \sqrt{n}n^ne^{-n}$, but I'll leave that up to you should you need that.

$\endgroup$
  • $\begingroup$ Thanks @vrugtehagel ! I wanted to avoid Stirling approximation, because it is still hard to evaluate numerically. BTW you used Stirling formula for $((n-m)/2)!$ which does not have to be large. $\endgroup$ – WoofDoggy Mar 15 '18 at 14:15
  • $\begingroup$ It is, but a lot gets cancelled. And yeah, $(n-m)/2$ doens't have to be large but it's quite a good approximation early on as well, and as I said it can be bounded below and above should the need be. In the end we only got some powers and a root, so evaluation wise I'm not sure if we can make this any easier without losing significant accuracy. $\endgroup$ – vrugtehagel Mar 15 '18 at 14:46
  • $\begingroup$ Your formula works pretty well! $\endgroup$ – WoofDoggy Mar 16 '18 at 20:27
0
$\begingroup$

Another way to reason, pretty advanced though, is to use Gamma function together with a Taylor series at infinity:

$$\binom{\frac{n+m}{2}}{m} \sim \left(\frac{1}{n}\right)^{-m} \left(\frac{2^{-m}}{m \Gamma (m)}+\frac{2^{-m}}{\Gamma (m) n}+O\left(\left(\frac{1}{n}\right)^2\right)\right)$$

$$\binom{n+m}{m}^{-1} \sim \left(\frac{1}{n}\right)^m \left(m \Gamma (m)+\frac{-\frac{\Gamma (m) m^3}{2}-\frac{\Gamma (m) m^2}{2}}{n}+O\left(\left(\frac{1}{n}\right)^{3/2}\right)\right)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.