Combinatorial interpretation of an alternating binomial sum

Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove this will be appreciated but a combinatorial solution is greatly preferred. Thanks for your help.

Solution 1:

Rewrite the identity with the index of summation changed from $i$ to $j$ where $j=i-k+1$: $$\sum_{j=1}^{n+1-k}(-1)^{j-1}\binom{n+1}{k+j}\binom{k+j-1}k=1.$$ Define a "good word" to be a word of length $n+1$ over the alphabet $\{A,B,C\}$ satisfying the conditions: there are exactly $k$ $C$'s, there is at least one $B$, and the first $B$ precedes all the $C$'s.

If $j$ is the number of $B$'s in a good word, then we must have $1\le j\le n+1-k$; moreover, the number of good words with exactly $j$ $B$'s is given by the expression $$\binom{n+1}{k+j}\binom{k+j-1}k.$$ The combinatorial meaning of the identity is that the number of good words with an odd number of $B$'s is one more than the number of good words with an even number of $B$'s. Here is a bijective proof of that fact.

Let $w$ be the word consisting of a single $B$ preceded by $n-k$ $A$'s and followed by $k$ $C$'s; this is a good word with an odd number of $B$'s. Let $W$ be the set of all good words different from $w$; we have to show that $W$ contains just as many words with an odd as with an even number of $B$'s. To see this, observe that the operation of switching the last non-$C$ letter in a word (from $A$ to $B$ or from $B$ to $A$) is an involution on $W$ which changes the parity of the number of $B$'s.

Solution 2:

I haven't yet come up with a combinatorial proof, but a proof using induction and the binomial formula is straightforward enough.

We fix $k \geqslant 0$ and use induction on $n \geqslant k$. The base case $n = k$ is simply

$$\sum_{i=k}^k (-1)^{i-k}\binom{i}{k}\binom{k+1}{i+1} = (-1)^0 \binom{k}{k}\binom{k+1}{k+1} = 1.$$

For the induction step, we have

$$\begin{align} \sum_{i=k}^{n+1} (-1)^{i-k}\binom{i}{k}\binom{n+2}{i+1} &= \sum_{i=k}^{n+1} (-1)^{i-k}\binom{i}{k}\left\lbrace \binom{n+1}{i+1} + \binom{n+1}{i}\right\rbrace\\ &=\sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i+1} + \sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i}\\ &=\underbrace{\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i+1}}_1 + \underbrace{\sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i}}_{m(k,n)} \end{align}$$

where in the first sum on the right the term for $i = n+1$ vanishes since $\binom{n+1}{n+1+1} = 0$ and the remainder is the sum for $n$, which is $1$ by the induction hypothesis.

It remains to see that $m(k,n) = 0$. But that is the coefficient of $x^k$ in

$$\begin{align} x^{n+1} &= \bigl(1 - (1-x)\bigr)^{n+1}\\ &= \sum_{i=0}^{n+1} (-1)^i\binom{n+1}{i}(1-x)^i\\ &= \sum_{i=0}^{n+1} \sum_{k=0}^i (-1)^{i+k}\binom{i}{k}\binom{n+1}{i}x^k\\ &= \sum_{k=0}^{n+1}\left(\sum_{i=k}^{n+1}(-1)^{i+k}\binom{i}{k}\binom{n+1}{i}\right)x^k, \end{align}$$

since $(-1)^{i+k} = (-1)^{i-k}$. We have $k \leqslant n < n+1$, hence the coefficient is $0$.

Solution 3:

This is a combinatorial proof of $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ It can be rearranged to $$\sum_{i=k+2t } \binom{i}{k} \binom{n+1}{i+1} = 1+ \sum_{i=k+1+2t} \binom{i}{k} \binom{n+1}{i+1} $$

I prefer to talk about choosing $i$ elements from a set whith $n$ elements to choosing $i+1$ elements from a set with $n+1$ elements so I substitute $i$ by $i-1$, $k$ by $k-1$ and $n$ by $n-1$ and get $$\sum_{i=k+2t } \binom{i-1}{k-1} \binom{n}{i} = 1+ \sum_{i=k+1+2t} \binom{i-1}{k-1} \binom{n}{i} \tag{1} $$

One well known interpretation of $\binom{n}{i}$ is as the number of subsets with $i$ elements of the set $ \{1,2,\ldots,n \}$.

if $n=9$ then $\{2,3,4,6,8\}$ is a subset with $i=5$ elements of $\{1,2,3,4,5,6,7,8,9\}$. Note that in the notation of the subsequence we find $i-1=4$ commas (","). Let's select two of this commas an replace them by "} {". We get $\big\{\{2\}\;\{3,4\}\;\{6,8\}\big\}$ if we replace the first and the third comma. So $\binom{i-1}{k-1}$ can be interpreted as the number of the ways a set with $i$ elements can be splitted into $k$ nonempty subsets $ A_r$ such that for each pair A, B of such subsets the following holds: $$(a \lt b, \;\; \forall a \in A, \forall b \in B) \;\;\text{or} \;\; (a \gt b, \;\; \forall a \in A, \forall b \in B)$$

The product $\binom{i-1}{k-1} \binom{n}{i}$ can be interpreted as the number of ways we can find $k$ subsets $A_j$ of $\{1,2,\ldots,n \}$ such that $$ A_r \cap A_s = \emptyset, \forall 1 \le r \lt s \le k \tag{2a}$$ $$ a_r \lt a_s, \forall a_r \in A_r, \forall a_s \in A_s, 1 \le r \lt s \le k \tag{2b}$$ $$ \sum_{r=1}^{k}|A_r|=i \tag{2c}$$

We call the set of all $\{A_1,\ldots \}$ that satisfy $(2)$ as $\Omega_{n,k,i}$. We have already seen that $$|\Omega_{n,k,i}|=\binom{i-1}{k-1} \binom{n}{i} \tag{3}$$ Because of $(2c)$ $$\Omega_{n,k,i} \cap \Omega_{n,k,j} = \emptyset, \; \; \forall i \ne j \tag{4}$$

We define $$\Omega_{n,k}'' = \cup_{i=k+2t , i \le n,t \in \mathbb{N_0}} \Omega_{n,k,i}$$ and $$\Omega_{n,k}' = \cup_{i=k+1+2t , i \le n,t \in \mathbb{N_0}} \Omega_{n,k,i}$$ and $$\Omega_{n,k} = \cup_{i=k}^{n} \Omega_{n,k,i}= \Omega_{n,k}'' \cup \Omega_{n,k}'$$

It follows from $(4)$ and $(3)$ that $$|\Omega_{n,k}''| = \sum_{i=k+2t , i \le n,t \in \mathbb{N_0}} \binom{i-1}{k-1} \binom{n}{i}$$ an $$|\Omega_{n,k}'| = \sum_{i=k+1+2t , i \le n,t \in \mathbb{N_0}} \binom{i-1}{k-1} \binom{n}{i}$$

So to prove $(1)$ we have to show that there is a bijection $\phi$ from $\Omega_{n,k}'' \backslash \{\text{one element}\}$ to $\Omega_{n,k}'$. Let $\omega=\{A_1,\ldots, A_k\}$ an element from $\Omega_{n,k}$.

• If $n \notin A_k$ we define $\phi(\{A_1,\ldots, A_{k-1}, A_k\})=\{A_1,\ldots, A_{k-1}, A_k \cup \{n\} \}$
• If $n \in A_k$ and $ A_k \ne \{n\}$ we define $\phi(\{A_1,\ldots, A_{k-1}, A_k\})=\{A_1,\ldots, A_{k-1}, A_k \backslash \{n\} \}$

$\phi$ defined so far is a bijection from $\Omega_{n,k}'' \backslash \Theta_k $ to $\Omega_{n,k}' \backslash \Theta_k $. $\Theta_k $ is $\{A_1,\ldots, A_{k-1}, \{n\} \}$

But if $\omega \in \Theta_n$ there is a problem. $A_k \backslash \{n\}= \emptyset$ and $\{A_1,\ldots, A_{k-1}, \emptyset \} $ is not in $\Omega_{n,k}$. How can we extend $\phi$ to $\Theta_k$?

Recursively!

• If $n-1 \notin A_{k-1}$ we define $\phi(\{A_1,\ldots, A_{k-2}, A_{k-1}, \{n\} \})=\{A_1,\ldots, A_{k-2}, A_{k-1}\cup \{n-1\}, \{n\} \}$
• If $n-1 \in A_{k-1}$ and $ A_{k-1} \ne \{n-1\}$ we define $\phi(\{A_1,\ldots, A_{k-2}, A_{k-1}, \{n\} \})=\{A_1,\ldots, A_{k-2} , A_{k-1} \backslash \{n-1\} , \{n\} \}$

Now we have extended $\phi$ to $\Theta_n \backslash \Theta_{n-1}$. This process can be continued. Finally we arrive at the following definition for $\phi$:

For $\{A_1,\ldots, A_r\}, \;A_j \ne \{n-j\}, \; A_{r-t}=\{n-t\}, t=0,\ldots,j-1$ we define

• $\phi(\{A_1,\ldots, A_r\})=\{A_1,\ldots, A_{j-1},A_j \cup \{n-j\},\{n-j+1\},\ldots,\{n\}\}$ if $\{n-j\} \notin A_j $
• $\phi(\{A_1,\ldots, A_r\})=\{A_1,\ldots, A_{j-1},A_j \backslash \{n-j\},\{n-j+1\},\ldots,\{n\}\}$ if $\{n-j\} \in A_j $

$\phi$ is not defined for $\{\{n-k+1\},\ldots,\{n\}\}$ but it is a bijection from $\Omega_{n,k}'' \backslash \{\{n-k+1\},\ldots,\{n\}\}$ to $\Omega_{n,k}'$. Therefore $(1)$ holds.

an example

For $n=5$, $k=3$ we get the following mapping $\phi$

$$ \begin{array}{l|l} \hline{} \\ \omega & \phi(\omega) \\ \hline{} \\ \Omega_{5,3,3} \subset \Omega_{5,3}'' & \subset \Omega_{5,3}' \\ \hline{} \\ \{1\}\;\{2\}\;\{3\} & \{1\}\;\{2\}\;\{3,5\}\\ \{1\}\;\{2\}\;\{4\} & \{1\}\;\{2\}\;\{4,5\}\\ \{1\}\;\{2\}\;\{5\} & \{1\}\;\{2,4\}\;\{5\}\\ \{1\}\;\{3\}\;\{4\} & \{1\}\;\{3\}\;\{4,5\}\\ \{1\}\;\{3\}\;\{5\} & \{1\}\;\{3,4\}\;\{5\}\\ \{1\}\;\{4\}\;\{5\} & \{1,3\}\;\{4\}\;\{5\}\\ \{2\}\;\{3\}\;\{4\} & \{2\}\;\{3\}\;\{4,5\}\\ \{2\}\;\{3\}\;\{5\} & \{2\}\;\{3,4\}\;\{5\}\\ \{2\}\;\{4\}\;\{5\} & \{2,3\}\;\{4\}\;\{5\}\\ \{3\}\;\{4\}\;\{5\} & \text{no image} \\ \hline{} \\ \Omega_{5,3,4} \subset \Omega_{5,3}' & \subset \Omega_{5,3}'' \\ \hline{} \\ \{1\}\;\{2\}\;\{3,4\} & \{1\}\;\{2\}\;\{3,4,5\} \\ \{1\}\;\{2,3\}\;\{4\} & \{1\}\;\{2,3\}\;\{4,5\} \\ \{1,2\}\;\{3\}\;\{4\} & \{1,2\}\;\{3\}\;\{4,5\} \\ \{1\}\;\{2\}\;\{3,5\} & \{1\}\;\{2\}\;\{3\} \\ \{1\}\;\{2,3\}\;\{5\} & \{1\}\;\{2,3,4\}\;\{5\} \\ \{1,2\}\;\{3\}\;\{5\} & \{1,2\}\;\{3,4\}\;\{5\} \\ \{1\}\;\{2\}\;\{4,5\} & \{1\}\;\{2\}\;\{4\} \\ \{1\}\;\{2,4\}\;\{5\} & \{1\}\;\{2\}\;\{5\} \\ \{1,2\}\;\{4\}\;\{5\} & \{1,2,3\}\;\{4\}\;\{5\} \\ \{1\}\;\{3\}\;\{4,5\} & \{1\}\;\{3\}\;\{4\} \\ \{1\}\;\{3,4\}\;\{5\} & \{1\}\;\{3\}\;\{5\} \\ \{1,3\}\;\{4\}\;\{5\} & \{1\}\;\{4\}\;\{5\} \\ \{2\}\;\{3\}\;\{4,5\} & \{2\}\;\{3\}\;\{4\} \\ \{2\}\;\{3,4\}\;\{5\} & \{2\}\;\{3\}\;\{5\} \\ \{2,3\}\;\{4\}\;\{5\} & \{2\}\;\{4\}\;\{5\} \\ \hline{} \\ \Omega_{5,3,5} \subset \Omega_{5,3}'' & \subset \Omega_{5,3}' \\ \hline{} \\ \{1,2,3\}\;\{4\}\;\{5\} & \{1,2\}\;\{4\}\;\{5\} \\ \{1,2\}\;\{3,4\}\;\{5\} & \{1,2\}\;\{3\}\;\{5\} \\ \{1,2\}\;\{3\}\;\{4,5\} & \{1,2\}\;\{3\}\;\{4\} \\ \{1\}\;\{2,3,4\}\;\{5\} & \{1\}\;\{2,3\}\;\{5\} \\ \{1\}\;\{2,3\}\;\{4,5\} & \{1\}\;\{2,3\}\;\{4\} \\ \{1\}\;\{2\}\;\{3,4,5\} & \{1\}\;\{2\}\;\{3,4\} \\ \hline{} \end{array} $$

Solution 4:

Here is another algebraic proof. Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

The sum we are trying to evaluate is $$\sum_{k=j}^n (-1)^{k-j} {k\choose j} {n+1\choose k+1} = (n+1) \sum_{k=j}^n \frac{(-1)^{k-j}}{k+1} {k\choose j} {n\choose k}.$$ Now let $$A_1(z) = \sum_{k\ge 0} (-1)^{k-j} {k\choose j} \frac{z^k}{k!} = \frac{1}{j!} \sum_{k\ge j} (-1)^{k-j} \frac{z^k}{(k-j)!} \\= \frac{1}{j!} z^j \sum_{k\ge j} (-1)^{k-j} \frac{z^{k-j}}{(k-j)!} = \frac{1}{j!} z^j \exp(-z).$$ It then follows that $$ A(z) = \sum_{k\ge 0} \frac{(-1)^k}{k+1} {k\choose j} \frac{z^k}{k!} = \frac{1}{z} \left(C + \int A_1(z) dz\right)$$ with $C$ a constant to be determined.

Now it is not difficult to show (consult the end of this post) that $$\int A_1(z) dz = -\exp(-z) \sum_{q=0}^j \frac{z^q}{q!}$$ and we must have $$C = -[z^0] \left(-\exp(-z) \sum_{q=0}^j \frac{z^q}{q!} \right)= 1$$ so that $$A(z) = \frac{1}{z} \left(1 -\exp(-z) \sum_{q=0}^j \frac{z^q}{q!}\right).$$ We have now determined $A(z)$ for the convolution of the two generating functions.

We take $$B(z) = \sum_{k\ge 0} \frac{z^k}{k!} = \exp(z).$$ It follows that $$A(z) B(z) = \frac{1}{z} \left(\exp(z) - \sum_{q=0}^j \frac{z^q}{q!}\right).$$ Now applying the coefficient extraction operator we get for $n\ge j$ that $$(n+1) n! [z^n] A(z) B(z) = (n+1)! [z^{n+1}] \left(\exp(z) - \sum_{q=0}^j \frac{z^q}{q!}\right).$$ None of the terms from the sum contribute because $n+1>j$ so that we are left with $$(n+1)! [z^{n+1}] \exp(z) = (n+1)! \frac{1}{(n+1)!} = 1.$$

Verification. $$\left(-\exp(-z) \sum_{q=0}^j \frac{z^q}{q!}\right)' = \exp(-z) \sum_{q=0}^j \frac{z^q}{q!} - \exp(-z) \sum_{q=0}^{j-1} \frac{z^q}{q!} = \exp(-z) \frac{z^j}{j!}.$$