# Alternating sum of binomial coefficients times logarithm

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.

-
In 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. – Gerry Myerson Oct 12 '12 at 3:55
Sorry, I should have said that $m<n$. The problem still persists, though. – user44441 Oct 12 '12 at 5:53
@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$. – joriki Oct 12 '12 at 6:16
You can get binomial coefficients using \binom mj or {m\choose j}. – joriki Oct 12 '12 at 6:28
Ok, thanks. My first post, so please excuse the mistakes. – user44441 Oct 12 '12 at 14:32

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 $$\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) )$$ where $r=n-m$. Putting all this together we have: $$\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)) )$$

-

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} \,.$$

-
Isn't this a duplicate of @joriki's answer, posted 11 hours earlier? – Did Oct 12 '12 at 23:05
@did:Did you read what I wrote at the top of my answer. – Mhenni Benghorbal Oct 12 '12 at 23:09
I did. And?  – Did Oct 12 '12 at 23:21
Good that you did. – Mhenni Benghorbal Oct 12 '12 at 23:26
Do you consider you answered, even partly, my first comment? If not, why do you consider unnecessary to do so? Attitudes have consequences, you know... – Did Oct 13 '12 at 8:28

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.

-
I 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. – user44441 Oct 13 '12 at 2:36
@user44441: Hehe, that's nice :-) And you're welcome. – joriki Oct 13 '12 at 2:49