Prove that my operation is equivalent to $(n+1)!-1$

Question

I stumbled upon the following relationship with small values of $n$. I later verified its correctness with a python script.

$$f([1,2,\cdots,n]) = (n+1)!-1$$

This operation $f$ is defined on a set of integers. I am sure can be expressed using $\sum$ and $\prod$ but I was not able to frame it. I will try to illustrate what this operation is using examples.

If the set was $[a,b]$, then $f([a,b])$ would be $(a+b+ab)$. If the numbers were $[a,b,c]$, it would be $(a+b+c+bc+ab+ac+abc)$. In case of $[a,b,c,d]$, It would be $[(p_1+p_2+p_3+abcd)]$ where $p_1 = (a+b+c+d)$, $p_2 = (ab+ac+ad+bc+bd+cd)$ and $p_3 = (abc+abd+acd+bcd)$.

1) So if the set was $[x_1, x_2, \cdots, x_n]$ what would the closed form representation of $f([x_1, x_2, \cdots, x_n])$ be?

2) For the case that the set is $[1,2,3,\cdots,n]$ , Please prove that $$f([1,2,\cdots,n]) = (n+1)!-1$$

---

This is my attempt,

$$\sum_{i=1}^nx_i + \sum_{i\neq j}^nx_ix_j + \cdots + \prod_{i=1}^nx_i$$

For the case that the set is $[1,2,3,\cdots,n]$ (which is the case that is of special interest to me) I tried writing it as,

$$n! + n!\left ( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots \frac{1}{n} \right ) + n!\left ( \frac{1}{1\times2} + \frac{1}{1\times3} + \cdots + \frac{1}{1\times n} + \frac{1}{2\times 3} + \frac{1}{2\times 4} +\cdots \frac{1}{n(n-1)} \right ) + \cdots$$

---

Here is my implementation of the function $f$,

from random import randint
import math
n = 4

# index -> 0  to 198
s = list(range(1,n+1))

while(len(s)>1 and False):
    indexA = randint(0,len(s)-1)
    a = s[indexA]
    s.remove(a)

    indexB = randint(0,len(s)-1)
    b = s[indexB]
    s.remove(b)

    s.append(a+b+a*b)
    print(s)

# The only element left in the list
ans1 = s[0]
ans2 = math.factorial(n+1)-1
print("Final Answer = "+str(ans1)+"\n")
print("(n+1)! - 1 = "+str(ans2))

In case you are confused about the way I implemented this function, you can check out my motivativation for this question here.

Any suggestions to improve the question, propose tags is appreciated.

Answer 1

You have $$ f([a, b]) = a + b + ab = (1+a)(1+b) - 1 \\ f([a, b, c]) = a+b+c+bc+ab+ac+abc = (1+a)(1+b)(1+c) - 1 $$ and in general $$ f([x_1, x_2, \dots, x_n]) = (1+x_1)(1+x_2)\cdots(1+x_n) -1 $$ In particular $$ f([1, 2, \dots, n]) = 2 \cdot 3 \cdots (n+1) -1 = (n+1)! - 1 $$

Answer 2

Let

$$g(n)=f\left(\left[1,2,\dots,n\right]\right)+1$$

You can think of this as the same sum, but including the empty product.

Clearly:

$$g(0)=1=(0+1)!$$

Perhaps less obviously:

$$g(n+1)=g(n)+(n+1)g(n)$$

Since $g(n)$ contains exactly all the products that do not include $n+1$, and $(n+1)g(n)$ contain exactly all the products that do include $n+1$.

So it follows by induction that $g(n)=(n+1)!$

Answer 3

The different terms that you have in your sum are called the symmetrics polynoms here.

It's a classical way to link the racines of a polynom with its coefficients. Indeed in your big sum, the i-th term is a symmetric polynom that is equal to the i-th coefficient of your polynom (with a $(-1)^{n-i}$ factor).

In your case we can consider the polynom whose racines are 1,2...,n. And this polynom can also be expressed as follow:

$P(X)=(X-1)...(X-n)$,

Let's note $a_i$ the coefficient of $X^i$ in this polynom. We can now notice that

$P(-1) = (-1)^n(n+1)! = (-1)^n(1 + \sum_{i=0}^{n-1}(-1)^{n-k}a_k)$

and the term $\sum_{i=0}^{n-1}(-1)^{n-k}a_k$ is exactly your sum (convince yourself and check wikipedia page for help), and we finally find out that:

Your sum $= \sum_{i=0}^{n-1}(-1)^{n-k}a_k = (n+1)! -1$

Hope it helps.

Cheers,

Adam