Parallelogram Identity Proof (Using Stars and Bars Technique)

The parallelogram identity in Pascal's triangle states that, given an entry \({n \choose k}\) in Pascal's triangle, \({n \choose k}-1 = \) the sum of the entries included in the rectangle that is straight above entry \({n \choose k}\) and also includes the apex of Pascal's triangle. This equality can be expressed as a double sum as follows, $${n+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{n-k}{n-i-j \choose k-i}$$. 

We can prove this by using the stars and bars technique that we are familiar with. For easier explanation, let's first rewrite the double sum expression above in another form (but mathematically equivalent). Set \(r = n-k\), we have  $${r+k+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{r}{(k-i)+(r-j) \choose k-i}$$. 

Let's assume we have \((k+1)\) stars and \(r\) bars. As we have already known, \({r+k+1 \choose k+1}\) counts the number of different star-bar sequences. This implies that maybe we can try to interpret the RHS as another way to count almost the same thing (only differ by 1) in order to prove both sides are equal. 

Usually a sum expression in a combinatoric argument suggests that the ways of n choose k can be divided into multiple disjoint categories. We then try to get the counting result from each category and add them up to get the total number of ways of n choose k. Following this logic, a double sum may suggest that we can further divide each category into multiple subcategories. After we get the counting result from each subcategory, we add them up to get the result for each category. Then we add up all the results from each category to get the total number. 

In our case, we start by thinking of any arbitrary star-bar sequence as a sequence composed of four parts: some stars (at least zero stars)+some bars (at least one bar)+a star+ a sequence of mixed bars and stars. Our categorization is based on the first two parts. We first distribute \(i\) stars to the first part, and then distribute \(j\) bars to the second part. We cannot do anything about the third part. Finally when we get to the fourth part. We are left with \((r-j)\) bars and \((k-i)\) stars (remember the third part also takes 1 star so in total \((k+1)-i-1=k-i\). So the number of different star-bar sequences in the fourth part would be \((k-i)+(r-j) \choose k-i\). We then sum up \((k-i)+(r-j) \choose k-i\) for all possible combinations of \(i\) and \(j\) to get the total. 

There is only one problem for the argument above which will explain where there is a "-1" in the equation we are trying to prove. You may have noticed that on the RHS, the upper bound on \(i\) is \(k\) instead of \(k+1\). This is because we always want one star for the third part. But actually we can have no stars at all after the second part (such as *****||||)and this is the case that we haven't included. Therefore, the number of different star-bar sequences using the RHS logic can be expressed as: $${r+k+1 \choose k+1}=\sum_{i=0}^{k}\sum_{j=1}^{r}{(k-i)+(r-j) \choose k-i} +1$$. Therefore  $${r+k+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{r}{(k-i)+(r-j) \choose k-i}$$.