Skip to main content
2 of 3
edited tags

A binomial product sum that turns out to be 1

The binomial product sum \begin{align*} \sum\limits_{\substack{i_1> i_2> \cdots > i_k\\i_1, i_2, \cdots, i_k \in \{1, 2, \cdots, n-1\}}}\binom{n}{i_1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots\binom{i_{k-1}}{i_k}\binom{i_k}{0} \end{align*} with the convention that if the summation is over an empty subset, then only $\binom{n}{0}$ occurs in the product. This formula gives the sequence of Fubini numbers on varying $n$ along $1,2,3,\ldots$. A justification for this appears in the page Closed form for a binomial product sum. Now I have a slightly modified question. The same binomial product sum with the following modification \begin{align*} \sum\limits_{\substack{i_1> i_2> \cdots > i_k\\i_1, i_2, \cdots, i_k \in \{1, 2, \cdots, n-1\}}}(-1)^{p+k+1}\binom{n}{i_1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots\binom{i_{k-1}}{i_k}\binom{i_k}{0} \end{align*} gives the constant sequence $1,1,1,\ldots$ for $n=1,2,3,\ldots$ as verified using the sagemath code posted here. The cancellations in the summation is not very insightful if one check some concrete example. Is there any way to say that this sum is indeed going to give 1 all the times? What could be a justification for this?