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

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("(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.

• Hint. In your last line use partial fractions to make a telescoping sum: $1/n(n+1) = 1/n - 1/(n+1)$. (I haven't read the question carefully, so perhaps this in no use at all.) Nov 18 '16 at 13:38

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$$

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)!$

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,