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

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: $$\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 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.
• Commented Jun 6, 2023 at 10:19

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$$

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.

• Great perspective! Just what does $\propto$ mean exactly? Hmm... I think it could be an equal sign?? Commented Jun 6, 2023 at 11:53
• So my sum is equal to 2 times the probability that when sampling an infinite stream of bits, I have sampled at most $k$ ones in the first $n+k+1$ bits. And the thing below the fraction line is 2 times the probability that in a stream of bits I have sampled exactly $k+1$ ones in the first $n+k+1$ bits and that the next bit is $0$. Or simply that I have sampled exactly $k+1$ ones in the first $n+k+1$ bits. Just placing this observation here... Commented Jun 6, 2023 at 12:09
• @donaastor it means proportional to :) Commented Jun 6, 2023 at 12:19