Would like to compute the following sum: $\sum_{j=1}^m (-1)^j \begin{pmatrix} m\\ j\end{pmatrix} \log(1 - j/n)$, where $1 \leq m < n$ are fixed integers. A similar sum has already been computed on Stackexchange at Limit of alternating sum with binomial coefficient, where the logarithmic term is $\log(a+bk)$; the answer is in terms of $r = a/b$ and involves the gamma function, $\Gamma(r)$. When I apply this to my situation, I get (as part of the answer) $a=1, b=-1/n$ and therefore, I get the term $\Gamma(r) = \Gamma(-n)$ which is not defined, since the gamma function has a pole there. Please help with the correct expression for the sum in my case.
Alternating sum of binomial coefficients times logarithm
-
2In your sum, the term with $j=m$ is going to give $\log0$ if $m=n$. Maybe this is why that other formula doesn't work for you --- your sum inherently involves an undefined term. – 2012-10-12
-
0Sorry, I should have said that $m
– 2012-10-12 -
0@user44441: There's an edit link under the question. Please fix the question itself; people shouldn't have to read through the comments to understand the question. Note that the result in the other question is asymptotic for large $m$, so Gerry's point is still relevant, since the asymptotic expansion doesn't know whether you're excluding $m=n$. – 2012-10-12
-
1You can get binomial coefficients using `\binom mj` or `{m\choose j}`. – 2012-10-12
-
0Ok, thanks. My first post, so please excuse the mistakes. – 2012-10-12
-
0Similar problem with identical title now posted to MO: http://mathoverflow.net/questions/109975/alternating-sum-of-binomial-coefficients-times-logarithm – 2012-10-18
3 Answers
We can extend the sum to $j=0$ since the summand is $0$ for $j=0$. We have
$$ \begin{align} \sum_{j=0}^m(-1)^j\binom mjj^l &=\left.\sum_{j=0}^m\left(q\frac{\partial}{\partial q}\right)^lq^j\binom mj\right|_{q=-1} \\ &=\left.\left(q\frac{\partial}{\partial q}\right)^l(1+q)^m\right|_{q=-1} \\ &=(-1)^mm!\left\{{l\atop m}\right\}\;, \end{align} $$
where $\left\{{l\atop m}\right\}$ is a Stirling number of the second kind.
This vanishes for $0\le l\lt m$, so expanding the logarithm yields a power series in $1/n$ with leading term $1/n^m$:
$$ \begin{align} \sum_{j=1}^m (-1)^j\binom mj\log(1 - j/n) &= -\sum_{j=0}^m (-1)^j\binom mj\sum_{l=1}^\infty\frac1l\left(\frac jn\right)^l \\ &= (-1)^{m+1}m!\sum_{l=m}^\infty\left\{{l\atop m}\right\}\frac{n^{-l}}l\;. \end{align} $$
Formally, we can also write
$$ \sum_{j=0}^m(-1)^j\binom mj\log(1 - j/n)=\log\left(1-\frac qn\frac{\partial}{\partial q}\right)(1+q)^m\;, $$
but I'm not sure whether that's of any use.
-
0I was hoping for a closed form expression (like the post I am referencing) which will likely involve the Gamma function. Interestingly enough, the original problem where this comes from starts out with exactly the sum, $\sum_{l=m}^\infty \left\{ \begin{matrix} l\\m \end{matrix} \right\} \frac{1}{\ell n^{\ell}$. But this approach may yet be helpful, thanks. – 2012-10-13
-
0@user44441: Hehe, that's nice :-) And you're welcome. – 2012-10-13
Here is an asymptotic expression for the above sum; thanks for all the help. This took a little time to figure out.
$$ \begin{aligned} \sum_{j=1}^{m} (-1)^{j} \binom mj {\log(1 - j/n)} &= \sum_{j=1}^m (-1)^j \binom mj (\log(n-j) - \log n) \\ &= \sum_{j=1}^m (-1)^j \binom mj \log(n-m + m-j) - \log n \sum_{j=1}^m (-1)^j \binom mj \\ & = \sum_{m-j = 0}^{m-1} \left((-1)^{m - (m-j)} {m \choose m-j} \log((n-m) + (m-j))\right) + \log n\\ & = \sum_{k = 0}^{m-1} \left((-1)^{m-k} \binom mk \log((n-m) + k)\right) + (-1)^m (-1)^m\log n \\ & = (-1)^m \sum_{k = 0}^{m} \left((-1)^{k} \binom mk \log((n-m) + k)\right) \end{aligned} $$ Letting $r=n-m$, we now estimate $\sum_{k=0}^{m} (-1)^{k} \binom mk \log(r+k)$. $$ \begin{aligned} \sum_{k=0}^{m} (-1)^{k} \binom mk \log(r+k) &= \sum_{k=0}^{m} (-1)^{k} \binom mk \int_1^{r+k} \frac{1}{x}\, dx \\ &= \sum_{k=0}^{m} (-1)^{k} \binom mk \int_0^1\,\, \sum_{j=1}^{r+k-1} \frac{1}{x+j}\, dx \\ &= \int_0^1 \,\, \sum_{j=1}^{r+m-1} \frac{1}{x+j} \sum_{k = \text{max} \{j+1-r,0\}}^m (-1)^k \binom mk \, dx \\ &= \int_0^1 \,\, \sum_{j=1}^{r+m-1} \frac{1}{x+j} \cdot (-1)^{j-r+1} {m-1\choose j-r}\, dx \\ &= \int_0^1 \,\, \sum_{j=r}^{r+m-1} \frac{1}{x+j} \cdot (-1)^{j-r+1} {m-1\choose j-r}\, dx \\ &= \int_0^1 \,\, \sum_{i=0}^{m-1} \frac{(-1)^{i+1} {m-1\choose i}}{x+r+i} \, dx, \qquad i = j-r \\ &= \int_0^1 \,\, \frac{-\Gamma(m+1) \Gamma(r+x)}{\Gamma(m+r+x+1)}\, dx %&= -\Gamma(m+1) \int_0^1 \,\, \frac{\Gamma(n-m+x)}{\Gamma(n+x+1)}\, dx \end{aligned} $$ We have the following estimate for the ratio of Gamma functions: $\Gamma(N)/\Gamma(N+x) = N^{-x}(1 + O(1/N))$. Therefore, $\displaystyle{\Gamma(r+x)/\Gamma(r+x+m+1) = (r+x)^{-m-1} (1 + O(1/r))}$. Plugging this back into the previous equation and integrating, we get \begin{equation} \sum_{k=0}^{m} (-1)^{k} \binom mk \log(r+k) = \frac{-\Gamma(m)}{m} \left( \frac{1}{r^m} - \frac{1}{(r+1)^m} \right) ( 1 + O(1/r) ) \end{equation} where $r=n-m$. Putting all this together we have: \begin{equation} \sum_{j=1}^{m} (-1)^{j} \binom mj \log(1 - j/n) = (-1)^{m+1} \frac{\Gamma(m)}{m} \left( \frac{1}{(n-m)^m} - \frac{1}{(n-m+1)^m} \right) ( 1 + O(1/(n-m)) ) \end{equation}
Yesterday, I posted my answer by mistake on the other post while I was supposed to post it here. Anyways, your case is a special case of the case, we are going to deal with.
Recalling the identity of Stirling numbers of the second kind in terms of the binomial,
$$\left\{\begin{matrix} n \\ m \end{matrix}\right\} = \frac{1}{m!}\sum_{j=0}^m (-1)^{m-j}{m \choose j } j^n\,. $$
Writing the sum as $$ \sum\limits_{k=1}^{n} (-1)^k {n \choose k} \ln(a) + \sum\limits_{k=1}^{n} (-1)^k {n \choose k} \ln(1+\frac{b k}{a})$$
$$ -\ln(a) + \sum\limits_{k=1}^{n} (-1)^k {n \choose k} \ln(1+\frac{b k}{a}) \,.$$
Expanding the $\ln(1+\frac{b k}{a})$ in terms of its Taylor series and interchanging the order of summation gives $$ -n!\,\sum_{m=1}^{\infty}{\left(\frac{b}{a}\right)}^{m}\frac{1}{m} \left(\frac{1}{n!}\sum\limits_{k=1}^{n} (-1)^{m-k} {n \choose k} k^m \right) = -n!\,\sum_{m=1}^{\infty}\left\{\begin{matrix} m \\ n \end{matrix}\right\} {\left(\frac{b}{a}\right)}^{m}\frac{1}{m} $$
$$ = -n!\,\sum_{m=1}^{\infty}\left\{\begin{matrix} m \\ n \end{matrix}\right\} {\left(\frac{b}{a}\right)}^{m}\frac{1}{m} \,,$$
$$ \Rightarrow \sum\limits_{k=1}^{n} (-1)^k {n \choose k} \ln(a+bk) = -\ln(a) -n!\,\sum_{m=1}^{\infty}\left\{\begin{matrix} m \\ n \end{matrix}\right\} {\left(\frac{b}{a}\right)}^{m}\frac{1}{m} \,. $$
-
1Isn't this a duplicate of @joriki's answer, posted 11 hours earlier? – 2012-10-12
-
0@did:Did you read what I wrote at the top of my answer. – 2012-10-12
-
0I did. And? $ $ – 2012-10-12
-
0Good that you did. – 2012-10-12
-
0I have a naive question about the identity you prove: if $a=1$ and $b=N$ (say), then the left side, at least nominally, would seem to be irrational or even transcendental while the right side is a sum of Stirling numbers (which are integers) and rational numbers, so the result will be rational. Just try for $n=2$ above, for instance. This doesn't seem correct to me. Perhaps I am making a mistake in understanding the formula? – 2012-10-13
-
0@user44441: The Stirling number is the wrong way around; $m$ and $n$ should be exchanged (compare the identity at the top of the post); then the series remains infinite (as in my answer) and the problem you pointed out is resolved. – 2012-10-13
-
0@user44441: There is a mistake, I need to correct it. – 2012-10-13
-
0@joriki: Thanks. – 2012-10-13
-
0@Downvoter: The mistake was corrceted! – 2012-10-13
-
4Do you consider you answered, even partly, my first comment? If not, why do you consider unnecessary to do so? Attitudes have consequences, you know... – 2012-10-13