# Purely combinatorial proof and simplification of identity involving factorials and summations

While trying to decompose factorials into summations, I came up with the following identity $$(n+2)! = 2^{n+1} + \sum\limits_{k=0}^{n-1}\sum\limits_{i=0}^{n-1-k}\sum\limits_{S \subseteq [2,\ldots,n+1-i]\text{ where }|S|=k}^{}2^{i+1}\prod\limits_{t \in S}^{}t$$

I'm looking for a purely combinatorial proof of the identity and a way to get rid of the product term (if possible) without using extremely large number of summations.

This is the way I derived the identity (for some background):

The identity can be shown by defining some function $f(i,j)$ as follows $$f(i,j)=\sum\limits_{S \subseteq [2,\ldots,i+1] \text{ where }|S|=j}^{}\prod\limits_{t \in S}^{}t$$ (assume $f(i,0)=1$) and noticing that $(n+2)! = f(n+1,n+1)$ follows the following recurrence $$f(n+1,n+1)=2(f(n,0)+f(n,1)+f(n,2)+\cdots+f(n,n))$$ obtained from Vieta's formulas i.e. an expansion of $g(x)=(2+x)(3+x)(4+x)\cdots(n+1+x)$

Then applying this recurrence on $f(i,i)$ recurrently in the above recurrence we get $$f(n+1,n+1)=2^{n+1} + \sum\limits_{k=0}^{n-1}\sum\limits_{i=0}^{n-1-k}2^{i+1}f(n-i,k)$$ and substituting $f(n-i,k)$ yields the desired identity.

Also, note that by fiddling with the recurrence in a different way (making it telescope), one can show that $$(n+2)!=2\sum\limits_{k=0}^{n-1}\sum\limits_{i=0}^{n-1-k}f(n-i,k) + \sum\limits_{j=0}^{n+1}j!$$

But I don't immediately see how this will be helpful.

• I cannot tell how you find "follows the following recurrence". Why do you multiply by 2? – Phira Feb 10 '14 at 13:37
• Consider the function $g(x)=(x+2)(x+3)\cdots(x+n)(x+n+1)$, note that setting $x=1$, gives $\frac{(n+2)!}{2}$. But we can also write the expression as $f(n,0)+f(n,1)+\cdots+f(n,n)$ from vita's formulas. (note the $i+1$ in the definition of $f(i,j)$). That's why I multiplied by $2$. – Obinna Okechukwu Feb 10 '14 at 15:15
• i.e. $\frac{(n+2)!}{2}= g(1)=f(n,0)+f(n,1)+\cdots+f(n,n)=\frac{f(n+1,n+1)}{2}$ – Obinna Okechukwu Feb 11 '14 at 14:26

The matrix of Eulerian-numbers might help here. There are two (only slightly) different definitions; let's use that of the matrix which begins with $$E=\small \begin{bmatrix} 1 & . & . & . & . & . \\ 1 & 0 & . & . & . & . \\ 1 & 1 & 0 & . & . & . \\ 1 & 4 & 1 & 0 & . & . \\ 1 & 11 & 11 & 1 & 0 & . \\ 1 & 26 & 66 & 26 & 1 & 0 \end{bmatrix}$$ One can observe, that the rowsums are the factorials (and this is in fact true even if the matrixsize is assumed as infinite, or better: "true for any size").
Now there are arbitrarily many possibilities to define some triangular matrix, whose rows sum up to the factorials; however this one is special in that the columns can be seen as finitely composed by the coefficients only of geometric series and their derivatives. So although the column-sums diverge obviously we can -with some argument- assign rational analytic expressions to the column-sums, even if some of them indicate the existence of poles.
For instance, if we attempt to sum the first columns, we arrive at the expression for the geometric series with quotient 1 $$s_0 =_{\mid q=1} {1 \over 1-q}$$ But this becomes more meaningful, if we assume the columns as coefficients of power series; so if we define some indeterminate row-vector of infinite size $V(x) = [1,x,x^2,x^3,...]$ then the dot-product $$V(x) \cdot E = Y$$ gives a vector $Y$ of geometric series in $x$ which are convergent for some small x (and important: for continuous intervals of x, so we'll be able to analytically continue our results) and can be expressed by rational expressions. So for instance $Y_0 = {1 \over 1-x}$ (where the suffix at $Y$ shall indicate the column.
For the next column we can observe the composition by the coefficients of the geometric series with quotient 2 and the derivative of that with quotient 1: $$[1,2,4,8,16,.... ]-[1,2,3,4,5,...] =[0,0,1,4,11,...]$$ The derivative of the geometric series in $x$ has still a simple rational expression $$g(x) = \sum_{k=0}^\infty x^k = {1\over 1-x} \\ g^{(1)}(x) = {1\over (1-x)^2}$$ so $$Y_1 = {1\over 1-2x} - {1\over (1- 1x)^2}$$ and this can be extended to each of the following columns.

Geometric series are analytically continuable even for the divergent case and equal their rational expression even in the divergent case with the exception of the one pole at $x=1$ .

So what we have now is that $$V(x) \cdot E = Y$$ for some small interval of $x$, continuable to the whole range except $x=1$ giving a well defined row-vector $Y$.

On the other hand, the row sums of $E$ are known to sum up to the factorials, so we might as well write $$E \cdot V(1)^\tau = \Gamma^\tau \qquad \qquad \text{ where } \Gamma = [0!,1!,2!,3!,...]$$

If we take this together, we have some serious argument (of course no proof yet) to expect that we can evaluate by exploiting the two ways of associativity of the matrix-product-expression $$(V(x) \cdot E) \cdot V(1)^\tau = Y \cdot V(1)^\tau \\ = V(x) \cdot (E \cdot V(1)^\tau) = V(x) \cdot \Gamma^\tau$$ for some meaningful $x$. For instance, if I insert $x=-1$ thus define the alternating series of the factorials, I arrive (either by convergence or at least by simple Eulersummation of the dotproduct) at $$Y \cdot V(1)^\tau = \sum_{k=0}^\infty Y_k \underset{\mathfrak E}{=} 0.59634736...$$ as a linear transformation of $$V(-1) \cdot \Gamma^\tau = \sum_{k=0}^\infty (-1)^k \cdot k!$$ which evaluates then as the "Gompertz-constant"(wikipedia,mathworld) and which was expected by that alternating sum.

This all shall only describe one exemplary meaningful way to introduce a linear composition of the factorials, usable for some number-theoric problems. I don't have the formal proofs at hand (and don't think I ever can complete the formal requirements - but this should be easy for any student of number-theory in say his/her 2'nd year), so I hope this answers your question. A more detailed discussion of mine is at that page in the entry for the Eulerian-matrixk (see page $10$ ff there; note that for that article I used the Pari/GP-convention for the vector/matrix-transpose $M \sim$ and I use also the vectors as column-vectors as default, while I say $V(x)$ as a row vector here. An even more involved earlier discussion can be found here)