Combinatorial Limit

485 Views Asked by At

I was studing about deadtimes in optical communications and I found this limit:

$$ \lim_{n\rightarrow\infty}\frac{1}{n}\sum_{q=0}^{\lceil\frac{n}{d+1}\rceil}\binom{n-(q-1)d}{q}, $$ where $d$ is a fixed positive integer.

Since there is a combinatoric form there, I think Stirling approximation may be useful, but I don't know even how to start.

Edit: Yes, as you made me see, this shouldn´t have a finite limit, I am interested though, in finding the dominant term if it is possible.

2

There are 2 best solutions below

0
On BEST ANSWER

For $n\geq2(d+1)$ we can conclude:

$$\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{q=0}^{\lceil\frac{n}{d+1}\rceil}\binom{n-(q-1)d}{q}\\ \geq\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{q=2}^{2}\binom{n-(q-1)d}{q}\\ =\lim_{n\rightarrow\infty}\frac{1}{n}\binom{n-d}{2}\\ =\lim_{n\rightarrow\infty}\frac{1}{n}\cdot\frac{(n-d)(n-d-1)}{2}\rightarrow\infty$$

0
On

It's not entirely clear your limit even exists, if just a single term in that summand is $O(n^2$) then the whole thing grows without bound, and for a fixed integer $d$ since every binomial coefficient has an upper index proportional to $n$ one should get every binomial coeiffient is of order $O(n^k)$ for some non negative integer $k$. Yet since the upper index in your summation is also proportional to $n$ this means that the limit either doesn't exist, is equal to zero or a finite number of binomial coefficients in your summation have order $O(n)$ while all the other binomial coefficients have order $O(1)$ but this seems rather insane too since the coeiffients are spread out in a proportional matter indicating that if any had order $O(n)$ there would I imagine not always be a finite number of them as the value of your integer $n$ grew larger. Now while I am pretty tired at the moment, I'm still confident you've probably made an error, a typo or otherwise left out some relevant information to this problem.