Skip to main content
10 of 10
edited tags
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Limit of a sum with binomial coefficients

Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$ $$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$ $$C_k = \frac{\sum_{i=1}^k(2k-2i-1){2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$ for $k\in\mathbb{N}$, where the binomial coefficients are to be taken as zero if any of the parameters are negative.

I want to prove that $S_k:=A_k+B_k+C_k$ is decreasing from $k=3$ and $S_k\to2/3$ as $k\to\infty$. I have been struggling with a formal mathematical proof for a few days, and I hope that somebody can point me to the right direction.

Note that based on the first 10000 values, the above statements seem to hold, and $A_k,B_k$ and $C_k$ seem to tend to $2/9$ as $k\to\infty$, furthermore, $A_k$ and $B_k$ are decreasing whereas $C_k$ is increasing from $k=3$. Also note that $B_k+C_k$ is simply

$$\frac{\sum_{i=1}^k(2k-i-1){2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}.$$

The reason for not making this simplification is that I found it interesting that each of $A_k,B_k$ and $C_k$ tends to $2/9$. It may be better to handle $B_k+C_k$ as a unite.

Motivation: This question is related to a preceding question. In the setting explained in the other question, $S_k$ is the probability of the marked red ball staying red in a random permutation of $(2k-1)$ balls. The above statements are already proven in an excellent answer to the preceding question. The aim of the present question is to give a new proof using $A_k,B_k,C_k$.

macat
  • 155
  • 8