The hockeystick identity is given by

The hockeystick identity is given by

The Correct Answer and Explanation is:

Here is the solution to the problem.

(a) Proof using Pascal’s identity

The hockey-stick identity is 

∑k=0r(n+kk)=(n+r+1r)∑k=0r​(kn+k​)=(rn+r+1​)

. This proof proceeds by repeatedly applying Pascal’s identity, which states 

(mj)+(mj−1)=(m+1j)(jm​)+(j−1m​)=(jm+1​)

.

The proof begins with the left-hand side (LHS) of the identity. The first term in the summation, 

(n0)(0n​)

, is equal to 1. Since 

nn

 is a positive integer, 

(n+10)(0n+1​)

 is also equal to 1. Thus, 

(n0)(0n​)

 can be replaced by 

(n+10)(0n+1​)

 without changing the value of the sum.

The LHS becomes:

(n+10)+(n+11)+(n+22)+⋯+(n+rr)(0n+1​)+(1n+1​)+(2n+2​)+⋯+(rn+r​)

Applying Pascal’s identity to the first two terms gives 

(n+10)+(n+11)=(n+21)(0n+1​)+(1n+1​)=(1n+2​)

. The sum is now:

(n+21)+(n+22)+(n+33)+⋯+(n+rr)(1n+2​)+(2n+2​)+(3n+3​)+⋯+(rn+r​)

Again, applying Pascal’s identity to the new first two terms gives 

(n+21)+(n+22)=(n+32)(1n+2​)+(2n+2​)=(2n+3​)

. This process, known as a telescoping sum, continues. Each step combines the first two terms into a single term. After 

r−1r−1

 steps, the sum is reduced to two terms:

(n+rr−1)+(n+rr)(r−1n+r​)+(rn+r​)

A final application of Pascal’s identity yields 

(n+r+1r)(rn+r+1​)

, which is the right-hand side of the identity.

(b) Proof by combinatorial argument

The identity is first rewritten using the symmetry property 

(NK)=(NN−K)(KN​)=(N−KN​)

. The original identity 

∑k=0r(n+kk)=(n+r+1r)∑k=0r​(kn+k​)=(rn+r+1​)

 becomes:

∑k=0r(n+kn)=(n+r+1n+1)k=0∑r​(nn+k​)=(n+1n+r+1​)

This form can be proven by a combinatorial argument. Consider the problem of counting the number of ways to choose a subset of 

n+1n+1

 objects from a set of 

n+r+1n+r+1

 distinct objects arranged in a line.

The right-hand side (RHS), 

(n+r+1n+1)(n+1n+r+1​)

, counts this number directly, by the definition of a combination.

The left-hand side (LHS) counts the same quantity by partitioning the selections into 

r+1r+1

 disjoint cases. The partition is based on the position of the leftmost object chosen from the line. Let the position of this object be 

pp

. The remaining 

nn

 objects must then be selected from the 

(n+r+1)−p(n+r+1)−p

 objects to its right.

For a selection to be possible, there must be at least 

nn

 objects to the right of position 

pp

. This implies 

(n+r+1)−p≥n(n+r+1)−p≥n

, which simplifies to 

p≤r+1p≤r+1

. The position 

pp

 can therefore range from 

11

 to 

r+1r+1

.

For each case where the leftmost chosen object is at position 

pp

, there are 

(n+r+1−pn)(nn+r+1−p​)

 ways to choose the other 

nn

 objects. Summing over all possible values of 

pp

 gives the total number of ways:

∑p=1r+1(n+r+1−pn)p=1∑r+1​(nn+r+1−p​)

By performing a change of index with 

k=r+1−pk=r+1−p

, as 

pp

 ranges from 

11

 to 

r+1r+1

, the index 

kk

 ranges from 

rr

 down to 

00

. The summation becomes 

∑k=0r(n+kn)∑k=0r​(nn+k​)

, which is the LHS. Since both sides count the same set of combinations, the identity is proven.