When this question was first posted I wrote two solutions, one a direct induction and the other using a rational function identity. Recently, in the course of recentering a power series around a zero in two ways, I realized that the compatibility of the two methods was equivalent to a nonobvious identity... exactly the one posted in this problem. It's presented here as a calculation with formal power series in two indeterminates.

Let $F(X) = \sum_{m \geq 0} a_mX^m$ in $\mathbf Z[[X]]$. The difference $F(X) - F(Y)$ in $\mathbf Z[[X,Y]]$ vanishes when $Y = X$, so it is divisible by $X-Y$. Let's factor out $X-Y$ from $F(X) - F(Y)$ in two ways.

Method 1: Factoring $X - Y$ out of each difference $X^m - Y^m$ and changing the order of summation, \begin{eqnarray*} F(X) - F(Y) & = & \sum_{m \geq 1} a_m(X^m-Y^m) \\ & = & (X-Y)\sum_{m\geq 1} a_m\sum_{\ell = 0}^{m-1}X^\ell Y^{m-1-\ell} \\ & = & (X-Y)\sum_{\ell \geq 0}\sum_{m \geq \ell+1}a_mX^\ell Y^{m-1-\ell} \\ & = & (X-Y)\sum_{\ell \geq 0}\sum_{m \geq 0}a_{m+\ell+1}X^\ell Y^{m}. \end{eqnarray*}

Method 2: Let's expand $F(X)$ as a series centered at $Y$ instead of $0$ and change the order of summation: \begin{eqnarray*} F(X) & = & \sum_{m \geq 0} a_m(X-Y+Y)^m \\ & = & \sum_{m \geq 0} a_m\sum_{k=0}^m \binom{m}{k}(X-Y)^kY^{m-k} \\ &= & \sum_{k \geq 0} \left(\sum_{m \geq k} a_m\binom{m}{k}Y^{m-k}\right)(X-Y)^k. \end{eqnarray*} The term at $k = 0$ is $\sum_{m\geq 0} a_mY^m = F(Y)$, so \begin{eqnarray*} F(X) - F(Y) & = & (X-Y)\sum_{k \geq 1}\sum_{m \geq k} a_m\binom{m}{k}Y^{m-k}(X-Y)^{k-1} \\ & = & (X-Y)\sum_{k \geq 0} \sum_{m \geq k+1} a_m\binom{m}{k+1}Y^{m-k-1}(X-Y)^{k} \\ & = & (X-Y)\sum_{k \geq 0} \sum_{m \geq k+1} a_m\binom{m}{k+1}Y^{m-k-1}\sum_{\ell=0}^k \binom{k}{\ell}X^\ell(-Y)^{k-\ell}. \end{eqnarray*} Let's change the order of summation again: \begin{eqnarray*} F(X)-F(Y) & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq \ell+1}\left(\sum_{k=\ell}^{m-1} a_m\binom{m}{k+1}\binom{k}{\ell}(-1)^{k-\ell}\right)X^\ell{Y}^{m-\ell-1} \\ & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq 0}\left(\sum_{k=\ell}^{m+\ell} a_{m+\ell+1}\binom{m+\ell+1}{k+1}\binom{k}{\ell}(-1)^{k-\ell}\right)X^\ell{Y}^{m} \\ & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq 0}\left(\sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}\right)a_{m+\ell+1}X^\ell{Y}^{m}. \end{eqnarray*}

Comparing this final expression with the one at the end of Method 1, we see that $$ a_{m+\ell+1} = \sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}a_{m+\ell+1}. $$ The coefficients in $F(X)$ were just used to illustrate the generality of the calculation, but we can now set them all equal to 1: $$ 1 = \sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}. $$ The product of binomial coefficients in the $k$th term can be rewritten to have $k$ in just one binomial coefficient and in an additional factor: $$ \binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell} = \binom{m+\ell+1}{\ell+1}\binom{m}{k}\frac{\ell+1}{\ell+1+k}. $$ Therefore $$ 1 = \sum_{k=0}^{m}\binom{m+\ell+1}{\ell+1}\binom{m}{k}\frac{\ell+1}{\ell+1+k}(-1)^{k} = \binom{m+\ell+1}{\ell+1}\sum_{k=0}^m\binom{m}{k}\frac{(\ell+1)(-1)^k}{\ell+1+k}. $$ Since $\ell$ is an arbitrary nonnegative integer and occurs throughout as $\ell+1$, rewrite $\ell+1$ as $n$ and we get the desired binomial coefficient identity.

When this question was first posted I wrote two solutions, one a direct induction and the other using a rational function identity. Recently, in the course of recentering a power series around a zero in two ways, I realized that the compatibility of the two methods is equivalent to a nonobvious identity... exactly the one posted here. It's presented below as a calculation with formal power series in two indeterminates.

Let $F(X) = \sum_{m \geq 0} a_mX^m$ in $\mathbf Z[[X]]$. The difference $F(X) - F(Y)$ in $\mathbf Z[[X,Y]]$ vanishes when $Y = X$, so it is divisible by $X-Y$. Let's factor out $X-Y$ from $F(X) - F(Y)$ in two ways.

Method 1: Factoring $X - Y$ out of each difference $X^m - Y^m$ and changing the order of summation, \begin{eqnarray*} F(X) - F(Y) & = & \sum_{m \geq 1} a_m(X^m-Y^m) \\ & = & (X-Y)\sum_{m\geq 1} a_m\sum_{\ell = 0}^{m-1}X^\ell Y^{m-1-\ell} \\ & = & (X-Y)\sum_{\ell \geq 0}\sum_{m \geq \ell+1}a_mX^\ell Y^{m-1-\ell} \\ & = & (X-Y)\sum_{\ell \geq 0}\sum_{m \geq 0}a_{m+\ell+1}X^\ell Y^{m}. \end{eqnarray*}

Method 2: Let's expand $F(X)$ as a series centered at $Y$ instead of $0$ and change the order of summation: \begin{eqnarray*} F(X) & = & \sum_{m \geq 0} a_m(X-Y+Y)^m \\ & = & \sum_{m \geq 0} a_m\sum_{k=0}^m \binom{m}{k}(X-Y)^kY^{m-k} \\ &= & \sum_{k \geq 0} \left(\sum_{m \geq k} a_m\binom{m}{k}Y^{m-k}\right)(X-Y)^k. \end{eqnarray*} The term at $k = 0$ is $\sum_{m\geq 0} a_mY^m = F(Y)$, so \begin{eqnarray*} F(X) - F(Y) & = & (X-Y)\sum_{k \geq 1}\sum_{m \geq k} a_m\binom{m}{k}Y^{m-k}(X-Y)^{k-1} \\ & = & (X-Y)\sum_{k \geq 0} \sum_{m \geq k+1} a_m\binom{m}{k+1}Y^{m-k-1}(X-Y)^{k} \\ & = & (X-Y)\sum_{k \geq 0} \sum_{m \geq k+1} a_m\binom{m}{k+1}Y^{m-k-1}\sum_{\ell=0}^k \binom{k}{\ell}X^\ell(-Y)^{k-\ell}. \end{eqnarray*} Let's change the order of summation again: \begin{eqnarray*} F(X)-F(Y) & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq \ell+1}\left(\sum_{k=\ell}^{m-1} a_m\binom{m}{k+1}\binom{k}{\ell}(-1)^{k-\ell}\right)X^\ell{Y}^{m-\ell-1} \\ & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq 0}\left(\sum_{k=\ell}^{m+\ell} a_{m+\ell+1}\binom{m+\ell+1}{k+1}\binom{k}{\ell}(-1)^{k-\ell}\right)X^\ell{Y}^{m} \\ & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq 0}\left(\sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}\right)a_{m+\ell+1}X^\ell{Y}^{m}. \end{eqnarray*}

Comparing this final expression with the one at the end of Method 1, we see that $$ a_{m+\ell+1} = \sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}a_{m+\ell+1}. $$ The coefficients in $F(X)$ were just used to illustrate the generality of the calculation, but we can now set them all equal to 1: $$ 1 = \sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}. $$ The product of binomial coefficients in the $k$th term can be rewritten to have $k$ in just one binomial coefficient and in an additional factor: $$ \binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell} = \binom{m+\ell+1}{\ell+1}\binom{m}{k}\frac{\ell+1}{\ell+1+k}. $$ Therefore $$ 1 = \sum_{k=0}^{m}\binom{m+\ell+1}{\ell+1}\binom{m}{k}\frac{\ell+1}{\ell+1+k}(-1)^{k} = \binom{m+\ell+1}{\ell+1}\sum_{k=0}^m\binom{m}{k}\frac{(\ell+1)(-1)^k}{\ell+1+k}. $$ Since $\ell$ is an arbitrary nonnegative integer and occurs throughout as $\ell+1$, rewrite $\ell+1$ as $n$ and we get the desired binomial coefficient identity.

When this question was first posted I wrote two solutions, one a direct induction and the other using a rational function identity. Recently, in the course of recentering a power series around a zero in two ways, I realized that the compatibility of the two methods provides a third explanation of this binomial coefficient identity, which I'll present as a calculation with formal power series in two indeterminates.

Let $F(X) = \sum_{m \geq 0} a_mX^m$ in $\mathbf Z[[X]]$. The difference $F(X) - F(Y)$ in $\mathbf Z[[X,Y]]$ vanishes when $Y = X$, so it is divisible by $X-Y$. Let's factor out $X-Y$ from $F(X) - F(Y)$ in two ways.

Method 1: Factoring $X - Y$ out of each difference $X^m - Y^m$ and changing the order of summation, \begin{eqnarray*} F(X) - F(Y) & = & \sum_{m \geq 1} a_m(X^m-Y^m) \\ & = & (X-Y)\sum_{m\geq 1} a_m\sum_{\ell = 0}^{m-1}X^\ell Y^{m-1-\ell} \\ & = & (X-Y)\sum_{\ell \geq 0}\sum_{m \geq \ell+1}a_mX^\ell Y^{m-1-\ell} \\ & = & (X-Y)\sum_{\ell \geq 0}\sum_{m \geq 0}a_{m+\ell+1}X^\ell Y^{m}. \end{eqnarray*}

Method 2: Let's expand $F(X)$ as a series centered at $Y$ instead of $0$ and change the order of summation: \begin{eqnarray*} F(X) & = & \sum_{m \geq 0} a_m(X-Y+Y)^m \\ & = & \sum_{m \geq 0} a_m\sum_{k=0}^m \binom{m}{k}(X-Y)^kY^{m-k} \\ &= & \sum_{k \geq 0} \left(\sum_{m \geq k} a_m\binom{m}{k}Y^{m-k}\right)(X-Y)^k. \end{eqnarray*} The term at $k = 0$ is $\sum_{m\geq 0} a_mY^m = F(Y)$, so \begin{eqnarray*} F(X) - F(Y) & = & (X-Y)\sum_{k \geq 1}\sum_{m \geq k} a_m\binom{m}{k}Y^{m-k}(X-Y)^{k-1} \\ & = & (X-Y)\sum_{k \geq 0} \sum_{m \geq k+1} a_m\binom{m}{k+1}Y^{m-k-1}(X-Y)^{k} \\ & = & (X-Y)\sum_{k \geq 0} \sum_{m \geq k+1} a_m\binom{m}{k+1}Y^{m-k-1}\sum_{\ell=0}^k \binom{k}{\ell}X^\ell(-Y)^{k-\ell}. \end{eqnarray*} Let's change the order of summation again: \begin{eqnarray*} F(X)-F(Y) & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq \ell+1}\left(\sum_{k=\ell}^{m-1} a_m\binom{m}{k+1}\binom{k}{\ell}(-1)^{k-\ell}\right)X^\ell{Y}^{m-\ell-1} \\ & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq 0}\left(\sum_{k=\ell}^{m+\ell} a_{m+\ell+1}\binom{m+\ell+1}{k+1}\binom{k}{\ell}(-1)^{k-\ell}\right)X^\ell{Y}^{m} \\ & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq 0}\left(\sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}\right)a_{m+\ell+1}X^\ell{Y}^{m}. \end{eqnarray*}

Comparing this final expression with the one at the end of Method 1, we see that $$ a_{m+\ell+1} = \sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}a_{m+\ell+1}. $$ The coefficients in $F(X)$ were just used to illustrate the generality of the calculation, but we can now set them all equal to 1: $$ 1 = \sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}. $$ The product of binomial coefficients in the $k$th term can be rewritten to have $k$ in just one binomial coefficient and in an additional factor: $$ \binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell} = \binom{m+\ell+1}{\ell+1}\binom{m}{k}\frac{\ell+1}{\ell+1+k}. $$ Therefore $$ 1 = \sum_{k=0}^{m}\binom{m+\ell+1}{\ell+1}\binom{m}{k}\frac{\ell+1}{\ell+1+k}(-1)^{k} = \binom{m+\ell+1}{\ell+1}\sum_{k=0}^m\binom{m}{k}\frac{(\ell+1)(-1)^k}{\ell+1+k}. $$ Since $\ell$ is an arbitrary nonnegative integer and occurs throughout as $\ell+1$, rewrite $\ell+1$ as $n$ and we get the desired binomial coefficient identity.

When this question was first posted I wrote two solutions, one a direct induction and the other using a rational function identity. Recently, in the course of recentering a power series around a zero in two ways, I realized that the compatibility of the two methods was equivalent to a nonobvious identity... exactly the one posted in this problem. It's presented here as a calculation with formal power series in two indeterminates.

Let $F(X) = \sum_{m \geq 0} a_mX^m$ in $\mathbf Z[[X]]$. The difference $F(X) - F(Y)$ in $\mathbf Z[[X,Y]]$ vanishes when $Y = X$, so it is divisible by $X-Y$. Let's factor out $X-Y$ from $F(X) - F(Y)$ in two ways.

Method 1: Factoring $X - Y$ out of each difference $X^m - Y^m$ and changing the order of summation, \begin{eqnarray*} F(X) - F(Y) & = & \sum_{m \geq 1} a_m(X^m-Y^m) \\ & = & (X-Y)\sum_{m\geq 1} a_m\sum_{\ell = 0}^{m-1}X^\ell Y^{m-1-\ell} \\ & = & (X-Y)\sum_{\ell \geq 0}\sum_{m \geq \ell+1}a_mX^\ell Y^{m-1-\ell} \\ & = & (X-Y)\sum_{\ell \geq 0}\sum_{m \geq 0}a_{m+\ell+1}X^\ell Y^{m}. \end{eqnarray*}

Method 2: Let's expand $F(X)$ as a series centered at $Y$ instead of $0$ and change the order of summation: \begin{eqnarray*} F(X) & = & \sum_{m \geq 0} a_m(X-Y+Y)^m \\ & = & \sum_{m \geq 0} a_m\sum_{k=0}^m \binom{m}{k}(X-Y)^kY^{m-k} \\ &= & \sum_{k \geq 0} \left(\sum_{m \geq k} a_m\binom{m}{k}Y^{m-k}\right)(X-Y)^k. \end{eqnarray*} The term at $k = 0$ is $\sum_{m\geq 0} a_mY^m = F(Y)$, so \begin{eqnarray*} F(X) - F(Y) & = & (X-Y)\sum_{k \geq 1}\sum_{m \geq k} a_m\binom{m}{k}Y^{m-k}(X-Y)^{k-1} \\ & = & (X-Y)\sum_{k \geq 0} \sum_{m \geq k+1} a_m\binom{m}{k+1}Y^{m-k-1}(X-Y)^{k} \\ & = & (X-Y)\sum_{k \geq 0} \sum_{m \geq k+1} a_m\binom{m}{k+1}Y^{m-k-1}\sum_{\ell=0}^k \binom{k}{\ell}X^\ell(-Y)^{k-\ell}. \end{eqnarray*} Let's change the order of summation again: \begin{eqnarray*} F(X)-F(Y) & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq \ell+1}\left(\sum_{k=\ell}^{m-1} a_m\binom{m}{k+1}\binom{k}{\ell}(-1)^{k-\ell}\right)X^\ell{Y}^{m-\ell-1} \\ & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq 0}\left(\sum_{k=\ell}^{m+\ell} a_{m+\ell+1}\binom{m+\ell+1}{k+1}\binom{k}{\ell}(-1)^{k-\ell}\right)X^\ell{Y}^{m} \\ & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq 0}\left(\sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}\right)a_{m+\ell+1}X^\ell{Y}^{m}. \end{eqnarray*}

Comparing this final expression with the one at the end of Method 1, we see that $$ a_{m+\ell+1} = \sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}a_{m+\ell+1}. $$ The coefficients in $F(X)$ were just used to illustrate the generality of the calculation, but we can now set them all equal to 1: $$ 1 = \sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}. $$ The product of binomial coefficients in the $k$th term can be rewritten to have $k$ in just one binomial coefficient and in an additional factor: $$ \binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell} = \binom{m+\ell+1}{\ell+1}\binom{m}{k}\frac{\ell+1}{\ell+1+k}. $$ Therefore $$ 1 = \sum_{k=0}^{m}\binom{m+\ell+1}{\ell+1}\binom{m}{k}\frac{\ell+1}{\ell+1+k}(-1)^{k} = \binom{m+\ell+1}{\ell+1}\sum_{k=0}^m\binom{m}{k}\frac{(\ell+1)(-1)^k}{\ell+1+k}. $$ Since $\ell$ is an arbitrary nonnegative integer and occurs throughout as $\ell+1$, rewrite $\ell+1$ as $n$ and we get the desired binomial coefficient identity.