4
$\begingroup$

I need to find a limit, or approximation for $\sum\limits_{k=1}^{n} (-1)^k {n \choose k} \log(a+bk)$ for, say, an $a,b\in (0,10)$. It is not so important what values $a$ and $b$ have. It would be already helpful for me to find a limit or an approximation for, say, $\sum\limits_{k=1}^{n} (-1)^k {n \choose k} \log(1+2k)$.

This sum arised in some analysis of stochastic processes and I have unfortunately almost not much knowledge in combinatorics and analysis to solve such equations. Thanks for any help.

  • 0
    @Coopi: because your account is not registered, when you change computers or IP addresses the system sometimes "forgets" who you are. Please consider registering your account: this will guarantee you the ability to edit and comment on your own questions.2012-04-04

2 Answers 2

7

Set $r=a/b$. We are fixing $r$ once and for all, so constants in big $O$'s can depend on $r$.

We are dealing with $\sum_{k=1}^{n} (-1)^k \binom{n}{k} \left( \log(1+k r^{-1}) + \log a \right) = - \log a + \sum_{k=0}^n (-1)^k \binom{n}{k} \left( \log(k+r) - \log r \right)$ We can get away with changing the lower bound of the sum from $1$ to $0$ because that term is $0$ anyway.

Following the approach from the previous question, $\sum_{k=0}^n (-1)^k \binom{n}{k} \left( \log(k+r) - \log r \right)= \int_{r}^{r+1} \frac{(n-1)! dx}{x(x+1)(x+2) \cdots (x+n-1)}.$ You should double check me on this, but I get that this time there is no extra $1/x$ term to keep track of. (Of course, if I got that wrong, just adjust the final answer by $\int_r^{r+1} dx/x = \log(r+1) - \log r$.) WARNING I think I might have missed a $(-1)^{n-1}$ here. At least, when I tried to do $n=2$ by hand, I got $-\int_r^{r+1} dx/x(x+1)$, not $\int_r^{r+1} dx/x(x+1)$. I'm not going to fix this because of the likelihood that I'd introduce new errors; just leaving a warning for you to check it carefully.

As before, this is $\int_{r}^{r+1} e^{-x \log n} (1+O(1/n)) \Gamma(x) dx = n^{-r}(1+O(1/n))\int_0^1 e^{-y \log n} \Gamma(r + y) dy.$

Now for a standard trick. That exponential means that almost all the contribution to the integral will come from $y$ near $0$. Make the change of variables $y \log n =z$, and then the significant contribution will be spread out over the entire $z$ range.

In other words: $\int_0^1 e^{-y \log n} \Gamma(1+r + y) dy = \frac{1}{\log n} \int_0^{\log n} e^{-z} \Gamma(r+z/\log n) dz.$ And $ \int_0^{\log n} e^{-z} \Gamma(r+z/\log n) dz = \int_0^{\log n} e^{-z} \left( \Gamma(r) + O(z/\log n) \right) dz = \Gamma(r) \int_0^{\log n} e^{-z} dz + O \left( \frac{1}{\log n} \int_0^{\infty} z e^{-z} \right)=$ $\Gamma(r)(1 - O(1/n)) + O(1/\log n) = \Gamma(r)(1+O(1/\log n)).$

Putting back the terms we dropped along the way, I get $\sum_{k=1}^n (-1)^k \binom{n}{k} \log(a+bk) = - \log a + \frac{\Gamma(r)}{n^r \log n} (1+O(1/\log n)).$ If you started your sum at $k=0$ instead of $k=1$, that $- \log a$ term would nicely go away, which makes me wonder whether that is what you intended.

If you need more terms, you should be able to get an asymtotic series in powers of $1/\log n$ by approximating $\Gamma(r+1+z/\log n)$ by more terms of its Taylor series.

  • 0
    You are right, I changed it to $\log(n)$. Thanks for your help.2012-04-04
0

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

  • 0
    This does not provide any information on the asymptotics of the original sum.2018-01-07