Variant of identity for a sum of binomial coefficient (Hockey-stick)

78 Views Asked by At

There is this well known Hockey-stick identity for binomial coefficients: $$\sum_{t=0}^k\binom{n+t}{t}=\binom{n+k+1}{k}$$ But what's interesting is that a very similar (approximate) identity holds for a thing similar to binomial coefficients. Let's define: $$\binom{n}{k}_2:=\frac{1}{2^n}\binom{n}{k},$$ which is something like the "normed" binomial coefficient. I have found this to hold for $k<n$: $$\sum_{t=0}^k\binom{n+t}{t}_2\approx\binom{n+k+1}{k+1}_2\frac{2k}{n-k}.$$ Yes, it is not too formal, I did it on a computer. But, I can formalize one conjecture: $$\frac{\sum_{t=0}^k\binom{n+t}{t}_2}{\binom{n+k+1}{k+1}_2}\to\frac{2c}{1-c}\hspace{12pt}\text{as}\hspace{12pt}n\to\infty,$$ where $0<c<1$ is a fixed constant and $k=\lfloor cn\rfloor$.

I am not very qualified for this but I am eager to understand this phenomenon. I tried to derive this using generating functions for $\binom{n+k}{k}$ and $\binom{n+k}{k}_2$, but I failed to make it to the end. Any insight is very welcome.

Progress:

With the insight of Rezha Adrian's answer, we have arrived at: $$\frac{\sum_{t=0}^k\binom{n+t}{t}_2}{\binom{n+k+1}{k+1}_2}=2\frac{\sum_{t=0}^k\binom{n+k+1}{t}}{\binom{n+k+1}{k+1}}.$$ With the substitutions: $n\leftarrow n+k+1$ and $k\leftarrow k+1$ we get the equivalent of: $$\frac{\sum_{t=0}^{k-1}\binom{n}{t}}{\binom{n}{k}}\to\frac{c}{1-2c},$$ where $k<\frac{n}{2}$ and $c=\frac{k}{n}$ is constant.
1

There are 1 best solutions below

3
On

Disclaimer

Incomplete solution, just some ideas

Combinatorial Argument

Toss a fair coin repeatedly until you get $n+1$ tails. The probability of tossing the coin a total of $n+k+1$ times is given below:

$$ P = \frac{1}{2^{n+k+1}}\binom{n+k}{n}=\frac{1}{2}\binom{n+k}{k}_{2} $$

Following the probability argument, we have :

$$ \frac{1}{2}\sum_{t=0}^{\infty}\binom{n+t}{t}_{2} = 1 $$

Connection with your observation

Suppose we toss the coins until either we have $n+1$ tails or we have tossed $n+k+1$ times, denote the probability of the former as $c$ and the later as $1-c$:

$$ \begin{aligned} \frac{1}{2}\sum_{t=0}^{k}\binom{n+t}{t}_{2}&\propto c \\\\ \sum_{t=k+1}^{n}\binom{n+k+1}{t}_{2}&\propto 1-c \end{aligned} $$

Then we have the following relation:

$$ \frac{\sum_{t=0}^{k}\binom{n+t}{t}_{2}}{\sum_{t=k+1}^{n}\binom{n+k+1}{t}_{2}} = \frac{2c}{1-c} $$

For the rest, I think it has something to do with limit as $n$ becomes larger and larger.