45
$\begingroup$

At MIT all departments have numbers, and math is 18. Last year MIT math majors produced a tee shirt that said ${i\choose 18}$ ("I choose 18") on the front, and on the back $$ \frac{34376687+1499084559i}{14485008384}. $$ With the more natural denominator $18!$ this is $$ \frac{15194495654000+662595375078000i}{18!}. $$ This suggests the question: for any $n\geq 1$ find a "nice" combinatorial interpretation of the real and imaginary parts of $i(i-1)(i-2)\cdots (i-n+1)=f_n+ig_n$. It is easy to express $f_n$ and $g_n$ as certain alternating sums of Stirling numbers of the first kind, but I don't consider this "nice." The $g_n$'s seem to alternate in sign beginning with $n=5$. The $f_n$'s alternate in sign up to $n=17$ and then seem to alternate in sign beginning with $n=18$. It is curious that $i(i-1)(i-2)(i-3)=-10$, a real number. One could ask the same question with $i$ replaced by any Gaussian integer $a+bi$. One can also ask about the asymptotic rate of growth of $f_n$ and $g_n$. Clearly $f_n^2+g_n^2\sim C\cdot (n-1)!^2$, so one would expect $f_n$ and $g_n$ to be roughly of the size of $(n-1)!$.

$\endgroup$
7
  • 2
    $\begingroup$ Thanks, Chandan, I have fixed the typo. If we consider $i$ as an indeterminate, then the coefficients are the Stirling numbers of the first kind, explaining the connection with these numbers. $\endgroup$ Dec 14, 2012 at 2:10
  • 5
    $\begingroup$ Thank you for not asserting that "This begs the question:" which is too useful a phrase in mathematical discussion to sacrifice to common usage. cafepress.com/begthequestion.38045148 $\endgroup$ Dec 14, 2012 at 2:51
  • 11
    $\begingroup$ The asymptotics can be obtained from the complex Stirling's formula. In particular, the $f_n$ and $g_n$ will usually alternate in sign, because ${i \choose n} \left/ {i \choose n-1} \right.$ is $\frac{i+1}{n} - 1$ which is nearly $-1$, but there'll be infinitely many exceptions (the next two are $g_{82},g_{83}>0$ and $f_{396},f_{397}>0$). I don't know of combinatorial interpretations, but do recognize that the identity $i(i-1)(i-2)(i-3) = -10$ is related with the identity $\tan^{-1}\frac12 + \tan^{-1}\frac13 = \frac\pi4$ that yields the earliest polynomial-time algorithm for computing $\pi$. $\endgroup$ Dec 14, 2012 at 3:44
  • 1
    $\begingroup$ One idea would be to promote the identity $(a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2$ to a bijection, then apply that bijection $n$ times. The minus sign is problematic... $\endgroup$ Dec 14, 2012 at 4:11
  • 4
    $\begingroup$ Not really relevant to this question, but if $a$ and $b$ are integers and $\binom{a+bi}{k}= c+di$, where $c$ and $d$ are rational, then every prime dividing the denominator of $c$ or $d$ is congruent to 2 or 3 modulo 4. $\endgroup$
    – Ira Gessel
    Dec 14, 2012 at 14:58

2 Answers 2

27
$\begingroup$

Asymptotics: Lets look at the quantity

$$S(n)=(-1)^{n}(n+1)\binom{i}{n+1}=i\prod_{k=1}^{n+1}\left(1-\frac{i}{k}\right).$$ It's just your binomial coefficient above with the $(-1)^{n+1}$ factored in, and an extra $n+1$ so it factors nicely as a product.

Claim: We have that

$$S(n)=\sqrt{\frac{\sinh{\pi}}{\pi}}e^{iC_{0}}e^{-i\log n}\left(1+O\left(\frac{1}{n}\right)\right),$$ where

$$C_{0}=\frac{-\pi}{2}-1+\int_0^\infty \frac{\{x\}}{1+x^2}dx =\arg(\Gamma(i))\approx -1.872.$$

In particular, the angle moves around the circle like $\log n$.

Application to your question: The above claim shows that $$f_{n+1} = (-1)^{n+1} n! \sqrt{\frac{\sinh{\pi}}{\pi}}\cos(-\log n+C_0)\left(1+O\left(\frac{1}{n}\right)\right)$$ and $$g_{n+1} \sim (-1)^{n+1} n! \sqrt{\frac{\sinh{\pi}}{\pi}} \sin(-\log n+C_0)\left(1+O\left(\frac{1}{n}\right)\right).$$

In particular, the ratio $g_n/f_n$ can be made arbitrarily large or small.

Proof of the claim: We first note that the size is

$$\sqrt{\prod_{k=1}^{n}\left(1+\frac{1}{k^{2}}\right)}=\sqrt{\prod_{k=1}^{\infty}\left(1+\frac{1}{k^{2}}\right)}+O\left(\frac{1}{n}\right).$$ To evaluate this product, recall the Weierstrass product for the Gamma function $$\left(\Gamma(z)\right)^{-1}=ze^{\gamma z}\prod_{k=1}^{\infty}\left(1+\frac{z}{k^{2}}\right)e^{-\frac{z}{r}}.$$ From this it follows that $$\frac{1}{|\Gamma(i)|^{2}}=\frac{1}{\Gamma(i)\Gamma(-i)}=\prod_{k=1}^{\infty}\left(1+\frac{1}{k^{2}}\right).$$ Using the identity $$\Gamma(x)\Gamma(-x)=-\frac{\pi}{x\sin\left(\pi x\right)},$$ we now have that $$\frac{1}{\Gamma(i)\Gamma(-i)}=\frac{-i\sin(i\pi)}{\pi}=\frac{\sinh(\pi)}{\pi},$$ which gives rise to the $\sqrt{\frac{\sinh(\pi)}{\pi}}$ term. Moving on to the evaluation of the angle, by looking at each triangle, and noting that the argument is additive when multiplied, we get that the argument equals

$$-\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right).$$

The negative sign arises since we are working in the fourth quadrant. By looking at the Taylor series for $\tan^{-1}$ we see that the above is $\log n+O(1)$, however, I would like to compute this argument more precisely, and obtain the constant. Lets compare our $\tan^{-1}$ series to the harmonic series. Rewriting things in terms of a Riemann Stieltjes integral, and using summation by parts, we have that

$$\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right)=\int_{0}^{n}\tan^{-1}\left(\frac{1}{x}\right)d\left[x\right]=[n]\tan^{-1}(1/n)\int_{0}^{n}\frac{\left[x\right]}{1+x^{2}}dx. $$

Pulling out the main term with the identity $[x]=x-\{x\}$, the above equals

$$\int_{0}^{n}\frac{x}{1+x^{2}}dx-\int_{0}^{n}\frac{\{x\}}{1+x^{2}}dx.$$

Since the first integral evaluates to $\frac{1}{2}\log(1+x^2)$, we have that $$\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right)=\log n +1-\int_0^\infty \frac{\{x\}}{1+x^2}dx +O\left(\frac{1}{n}\right).$$

Acknowledgements: I would like to thank Noam Elkies for pointing out that $$\prod_{k=1}^\infty \sqrt{1+\frac{1}{k^2}}=\frac{1}{|\Gamma(i)|}=\sqrt{\frac{\sinh(\pi)}{\pi}}$$ in the comments.

Edit: Fixed the constants appearing. Interestingly $$\Gamma(i)=\sqrt{\frac{\pi}{\sinh{\pi}}}\exp\left(i\left(\frac{-\pi}{2}-1+\int_0^\infty \frac{\{x\}}{1+x^2}dx \right)\right).$$

$\endgroup$
3
  • 7
    $\begingroup$ A closed form for $C_1 = 1.91731...$ is $1/|\Gamma(i)| = \sqrt{\frac{\textstyle\sinh\pi}{\textstyle\pi}}$. $\endgroup$ Dec 14, 2012 at 6:12
  • $\begingroup$ @Noam D. Elkies: Thank you for pointing this out. I have updated my answer and added a proof. $\endgroup$ Dec 14, 2012 at 6:56
  • 1
    $\begingroup$ Thanks for the edit and acknowledgement. One correction: it's the product over $k\geq 1$ of $\sqrt{1+\frac1{k^2}}$, not of $1+\frac1{k^2}$, that's equal to $1/|\Gamma(i)| = \sqrt{\frac{\textstyle\sinh\pi}{\textstyle\pi}}$. $\endgroup$ Dec 14, 2012 at 16:38
24
$\begingroup$

There is no need to reinvent the wheel by estimating $\prod_{k<n}(1+\frac1{k^2})$. The asymptotic formula for $f_n + i g_n$ follows readily from Stirling's approximation (as I already noted in my comment to the original question), and indeed the same is true for the asymptotics as $n \rightarrow \infty$ of $w \choose n$ for any $w \in {\bf C}$; the answer is simply

$$ \phantom{*0000000000000000000} {w \choose n} = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) \frac{(-1)^n}{\Gamma(-w)} n^{-w-1} \phantom{0000000000000000000}(*) $$

(and the $O(1/n)$ can be refined to an asymptotic series in powers of $1/n$). Note that this gives zero precisely for the values $w=0,1,2,3,\ldots$ for which $-w$ is a pole of $\Gamma$, which are also the $w$ for which ${w \choose n} = 0$ for sufficiently large $n$. For $w=i$, we recover the observed behavior: $\Gamma(i)$ is a complex number of absolute value $(\pi / \sinh \pi)^{1/2}$ [in general $$|\Gamma(it)| = (\Gamma(it)\Gamma(-it))^{-1/2} = \left(\frac \pi {t \phantom. \sinh \pi t} \right)^{1/2} $$ for real $t \neq 0$], and $n^{-w-1}$ is a complex number of absolute value $1/n$ that goes once around the origin when $n$ increases by a factor $e^{2\pi}$. Thus each of $\lbrace f_n \rbrace$ and $\lbrace g_n \rbrace$ alternates in sign outside an infinite sequence of exceptions that's asymptotically a geometric sequence with common ratio $e^\pi$.

To prove $(*)$, write $$ {w \choose n} = \frac{(-1)^n}{n!} \prod_{k=0}^{n-1} (k-w) = \frac{(-1)^n}{n!} \frac{\Gamma(n-w)}{\Gamma(-w)} = \frac{(-1)^n}{n\Gamma(-w)} \frac{\Gamma(n-w)}{\Gamma(n)}. $$ Now we understand $(-1)^n/n$, and the factor $1 / \Gamma(-w)$ is constant, so we're left with $\Gamma(n-w) / \Gamma(n)$. We apply the following form of Stirling's formula: there exists a constant $\varpi>0$ (known to equal $2\pi$, but we shall not need this) such that $$ \Gamma(z) = \bigl(1 + O(|z|^{-1}\bigr) z^z e^{-z} \sqrt{\varpi/z} $$ holds as $|z| \rightarrow \infty$ in the right half-plane, where $z^z = \exp (z \log z)$ and $\sqrt{\varpi/z}$ are defined using the principal branches of $\log z$ and $\sqrt z$. This gives $$ \frac{\Gamma(n-w)}{\Gamma(n)} = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) \frac{(n-w)^{n-w} e^{-(n-w)} (\varpi/(n-w))^{1/2}} {n^n e^{-n} (\varpi/n)^{1/2}} $$ $$ = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) \frac{(n-w)^{n-w}}{n^n} e^w \left(1-\frac{w}{n}\right)^{-1/2}. $$ Now the last factor is $1 + O(1/n)$; the factor $e^w$ is constant; and $$ (n-w)^{n-w} = (n-w)^{-w} (n-w)^n = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) n^{-w} (n-w)^n. $$ So we're left with $$ \frac{\Gamma(n-w)}{\Gamma(n)} = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) n^{-w} e^{-w} \left(1 - \frac{w}{n}\right)^n = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) n^{-w}. $$ This completes the proof of $(*)$ (and the cancellation in the last step leads me to suspect that even this use of Stirling is more complicated than necessary).

$\endgroup$
2
  • $\begingroup$ Thanks for sharing this answer. It is much cleaner, and it made me realize I previously have an error in the calculation of the constant $C_0$. (Also, it certainly looks much nicer to write $S(n)=\frac{1}{\Gamma(-i)}n^{−i}\left(1+O\left(\frac{1}{n}\right)\right).$) $\endgroup$ Dec 15, 2012 at 19:33
  • 3
    $\begingroup$ So ... it seems Stirling's approximation has a relation to Stirling numbers (of the first kind) ... $\endgroup$ Dec 20, 2013 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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