combinatorics - Combinatorial identity's algebraic proof without induction.

How would you prove this combinatorial idenetity algebraically without induction?

$$\sum_{k=0}^n { x+k \choose k} = { x+n+1\choose n }$$

Thanks.

Answer

Here is an algebraic approach. In order to do so it's convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g. \begin{align*} \binom{n}{k}=[z^k](1+z)^n \end{align*}

We obtain

\begin{align*} \sum_{k=0}^{n}\binom{x+k}{k}&=\sum_{k=0}^{n}\binom{-x-1}{k}(-1)^k\tag{1}\\ &=\sum_{k=0}^n[z^k](1+z)^{-x-1}(-1)^k \tag{2}\\ &=[z^0]\frac{1}{(1+z)^{x+1}}\sum_{k=0}^n\left(-\frac{1}{ z }\right)^k\tag{3}\\ &=[z^0]\frac{1}{(1+z)^{x+1}}\cdot \frac{1-\left(-\frac{1}{z}\right)^{n+1}}{1-\left(-\frac{1}{z}\right)}\tag{4}\\ &=[z^n]\frac{z^{n+1}+(-1)^n}{(1+z)^{x+2}}\tag{5}\\ &=(-1)^n[z^n]\sum_{k=0}^\infty\binom{-x-2}{k}z^k\tag{6}\\ &=(-1)^n\binom{-x-2}{n}\tag{7}\\ &=\binom{x+n+1}{n}\tag{8} \end{align*} and the claim follows.

Comment:

• 
  

  In (1) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

  
  



• 
  

  In (2) we apply the coefficient of operator.

  
  


• 
  

  In (3) we do some rearrangements by using the linearity of the coefficient of operator and we also use the rule \begin{align*} [z^{p-q}]A(z)=[z^p]z^{q}A(z) \end{align*}

  
  


• 
  

  In (4) apply the formula for the finite geometric series.

  
  


• 
  
  

  In (5) we do some simplifications and use again the rule stated in comment (3).

  
  


• 
  

  In (6) we use the geometric series expansion of $\frac{1}{(1+z)^{x+2}}$. Note that we can ignore the summand $z^{n+1}$ in the numerator since it has no contribution to the coefficient of $z^n$.

  
  


• 
  

  In (7) we select the coefficient of $z^n$.

  
  


• 
  

  In (8) we use the rule stated in comment (1) again.