follow up question to evaluating sum with counting formula

Question

I found that $\displaystyle\sum_{i=0}^{T}$$\displaystyle\sum_{j=0}^{P/2}\binom{i+j}{i}$ is equal to $\displaystyle\sum_{i=0}^{T}\sum_{j=0}^{\frac{P}{2}}\binom{i+j}{i}=\sum_{j=0}^{\frac{P}{2}}\binom{j+T+1}{T}=\binom{\frac{P}{2}+T+2}{T+1}-1$ by using the hockey-stick identity from this source https://en.wikipedia.org/wiki/Hockey-stick_identity

Question: I don't know where the $ -1$ comes from at the end of $\displaystyle\sum_{i=0}^{T}\sum_{j=0}^{\frac{P}{2}}\binom{i+j}{i}=\sum_{j=0}^{\frac{P}{2}}\binom{j+T+1}{T}=\binom{\frac{P}{2}+T+2}{T+1}-1$

Answer 1

To apply Hockey stick, you want to start at $ { T \choose T}=1$. However, you are starting at ${ T + 1 \choose T}$.

Answer 2

I suggest that you look at the "Hockey Stick" identity as a special case of the "Double Convolution" (upper & lower indices) $$ \eqalign{ & \sum\limits_{\left( { - m\, \le } \right)\,k\left( { \le \,n} \right)} {\left( \matrix{ a - k \cr n - k \cr} \right)\left( \matrix{ b + k \cr m + k \cr} \right)} = \cr & = \left( { - 1} \right)^{\,n + m} \sum\limits_k { \left( \matrix{ n - a - 1 \cr n - k \cr} \right)\left( \matrix{ m - b - 1 \cr m + k \cr} \right)} = \cr & = \left( { - 1} \right)^{\,n + m} \left( \matrix{ n + m - a - b - 2 \cr n + m \cr} \right) = \left( \matrix{ a + b + 1 \cr n + m \cr} \right) \quad \left| \matrix{ \;a,b \in R \hfill \cr \,n,m \in Z \hfill \cr} \right. \cr} $$ where it is important to assure that the summation index be free to vary over all the range in which the binomials are non-null: that's why I indicated the bounds in parenthesis.

Note that we are using the definition of the binomial as: $$ \binom{x}{n} = \left\{ {\matrix{ {{{x^{\,\underline {\,n\,} } } \over {n!}}} & {\left| {\;0 \le n \in \mathbb Z} \right.} \cr 0 & {{\rm else}} \cr } } \right. $$

So in your case $$ \eqalign{ & \sum\limits_{i = 0}^T {\sum\limits_{j = 0}^{P/2} {\left( \matrix{ i + j \cr i \cr} \right)} } \quad \quad \left( 0 \right) = \cr & = \sum\limits_{0\, \le \,j\, \le \,P/2} {\sum\limits_{0\, \le \,i\, \le \,T} {\left( \matrix{ i + j \cr i \cr} \right)} } \quad \quad \left( 1 \right) = \cr & = \sum\limits_{0\, \le \,j\, \le \,P/2} {\sum\limits_{\left( {0\, \le } \right)\,i\,\left( { \le \,T} \right)} {\left( \matrix{ T - i \cr T - i \cr} \right)\left( \matrix{ i + j \cr i \cr} \right)} } \quad \quad \left( 2 \right) = \cr & = \sum\limits_{0\, \le \,j\, \le \,P/2} {\left( \matrix{ T + j + 1 \cr T \cr} \right)} \quad \quad \left( 3 \right) = \cr & = \sum\limits_{0\, \le \,j\, \le \,P/2} {\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} \quad \left| {\;0 \le T + 1 \in \mathbb Z} \right.\quad \quad \quad \left( 4 \right) = \cr & = \sum\limits_{0\, \le \,j\,\left( { \le \,P/2} \right)} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} \quad \left| {\;0 \le P/2 \in \mathbb Z} \right.\quad \quad \quad \left( 5 \right) = \cr & = \sum\limits_{\left( { - 1\, \le } \right)\,j\,\left( { \le \,P/2} \right)} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} - \left. {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} \right|_{\,j = - 1} \quad \quad \left( 6 \right) = \cr & = \left( \matrix{ P/2 + T + 2 \cr P/2 + 1 \cr} \right) - 1 \quad \left| \matrix{ \;0 \le T + 1 \in \mathbb Z \hfill \cr \;0 \le P/2 \in \mathbb Z \hfill \cr} \right.\quad \quad \quad \left( 7 \right) = \cr & = \left( \matrix{ P/2 + T + 2 \cr T + 1 \cr} \right) - 1\quad \left| {\;0 \le P/2 \in \mathbb Z} \right.\quad \quad \left( 8 \right) = \cr & = \left( \matrix{ P/2 + T + 2 \cr T + 1 \cr} \right) - 1\quad \quad \left( 9 \right) \cr} $$ where the steps are:
- 1) it is preferrable to group the bounds of the sum as a unique condition;
- 2) for the inner sum, the lower bound $0 \le i$ is implicit in the binomial, we introduce a second binomial to make implicit the upper bound and virtually have no restriction on the index range;
- 3) we can then apply the double convolution;
- 4) we need the upper term of the binomial to be non-negative, so to apply symmetry;
- 5) we introduce again a binomial to make implicit the upper bound, but this need that $P/2$ be an integer;
- 6) the lower bound is not implicit in the 2nd binomial, we need it to start from $-1$, and make so by adding and then subtracting the summand corresponding to $j=-1$;
- 7) we apply the double convolution and recall the conditions on $T$ and $P$;
- 8) with those conditions we can apply symmetry and the condition on $P$ becomes implicit;
- 9) the binomial obtained is actually a polynomial in $P$, as such it interpolates $P$ also for real values of the same, and can therefore be extended to $P \in \mathbb R$.

--- additional notes ---

As told in the premise, to be able to apply the convolution (either simple or double) the range of the summation index shall be (formally) unrestricted or otherwise (practically) extend for the whole range in which the summand is not null.

So in step (4) we have that the summand is not null for $-1 \le j$, while the sum is given to start from $0=j$.
By adding the $\binom{P/2-j}{P/2-j}$ at step (5) we render implicit the upper bound at $P/2$ while for the lower bound we make $$ \eqalign{ & \sum\limits_{ - 1\, \le \,j} {} = \sum\limits_{ - 1\, \le \,j\, \le \, - 1} {} + \sum\limits_{0\, \le \,j\,} {} \quad \Rightarrow \cr & \Rightarrow \quad \sum\limits_{0\, \le \,j\,} {} = \sum\limits_{ - 1\, \le \,j} {} - \sum\limits_{\,j\, = \, - 1} {} \cr} $$ and pass to step (6), where now we can apply the convolution to the sum and reach yo (7).

I thought it was obvious, but ok, let's fill with data the sums above, starting from step (5). $$ \eqalign{ & \sum\limits_{0\, \le \,j\,\left( { \le \,P/2} \right)} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} \quad \quad (5) = \cr & = \sum\limits_{\left( { - 1\, \le } \right)\,j\,\left( { \le \,P/2} \right)} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} - \sum\limits_{ - 1\, \le \,j\, \le \, - 1} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} = \cr & = \sum\limits_{\left( { - 1\, \le } \right)\,j\,\left( { \le \,P/2} \right)} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} - \sum\limits_{\,j\, = \, - 1} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} = \cr & = \sum\limits_{\left( { - 1\, \le } \right)\,j\,\left( { \le \,P/2} \right)} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} - \left. {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} \right|_{\,j = - 1} \quad \quad (6) = \cr & = \sum\limits_{\left( { - 1\, \le } \right)\,j\,\left( { \le \,P/2} \right)} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} - \left( \matrix{ P/2 - \left( { - 1} \right) \cr P/2 - \left( { - 1} \right) \cr} \right)\left( \matrix{ T - 1 + 1 \cr - 1 + 1 \cr} \right) = \cr & = \sum\limits_{\left( { - 1\, \le } \right)\,j\,\left( { \le \,P/2} \right)} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} - \left( \matrix{ P/2 + 1 \cr P/2 + 1 \cr} \right)\left( \matrix{ T \cr 0 \cr} \right) = \cr & = \sum\limits_{\left( { - 1\, \le } \right)\,j\,\left( { \le \,P/2} \right)} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} - 1\; \cdot \;1 = \cr & = \sum\limits_{\left( { - 1\, \le } \right)\,j\,\left( { \le \,P/2} \right)} {\left( \matrix{ P/2 - j \cr P/2 - j \cr} \right)\left( \matrix{ T + j + 1 \cr j + 1 \cr} \right)} - 1\quad \quad (7) \cr} $$